{"problem":{"name":"H. Mr. Panda and SAD","description":{"content":"Mr. Panda owns many strings with only uppercase letters. He defines the happiness of a string to be the number of occurrence of \"_SAD_\" (SAD stands for Shanghai Algorithm Discussion) in the string.  ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10243H"},"statements":[{"statement_type":"Markdown","content":"Mr. Panda owns many strings with only uppercase letters. He defines the happiness of a string to be the number of occurrence of \"_SAD_\" (SAD stands for Shanghai Algorithm Discussion) in the string. \n\nOne day Mr. Panda broke one of his precious string inadvertently into $n$ pieces. The $i^(t h)$ piece had the string $s_i$ on it. He collected all the pieces and turned to Mr. Sheep for help. As Mr. Panda was very sad about the broken string, Mr. Sheep comforted him that if they concatenated all the pieces into a new string, the happiness of the string could be even greater than its original happiness value! But they really didn't know how to concatenate pieces to get the maximum happiness. It is your turn to help them again.\n\nThe first line of the input gives the number of test cases, $T$ $(1 <= T <= 100)$. $T$ test cases follow.\n\nEach test case begins with a line containing one integer $n$ $(1 <= n <= 2 times 10^5)$, the number of pieces Mr. Panda's precious string was broken into.\n\nIn the next $n$ lines, each line contains a string $s_i$ $(1 <= | s_i | <= 20)$ with only uppercase letters.\n\nIt is guaranteed that the sum of $n$ in all cases is not greater than $10^6$, and the sum of $| s_i |$ in all cases is not greater than $2 times 10^6$.\n\nFor each test case, output one line containing \"_Case #x: y_\", where _x_ is the test case number (starting from 1) and _y_ is the maximum happiness of the string that can be achieved by concatenating the pieces.\n\nFor the first sample, the new string can be concatenated as _SADSAD_, hence the happiness is 2.\n\nFor the second sample, the new string can be concatenated as _SSADD_, hence the happiness is 1.\n\nFor the third sample, the new string can be concatenated as _SA+DS+ADSA+D_ = _SADSADSAD_, hence the happiness is 3.\n\n## Input\n\nThe first line of the input gives the number of test cases, $T$ $(1 <= T <= 100)$. $T$ test cases follow.Each test case begins with a line containing one integer $n$ $(1 <= n <= 2 times 10^5)$, the number of pieces Mr. Panda's precious string was broken into.In the next $n$ lines, each line contains a string $s_i$ $(1 <= | s_i | <= 20)$ with only uppercase letters.It is guaranteed that the sum of $n$ in all cases is not greater than $10^6$, and the sum of $| s_i |$ in all cases is not greater than $2 times 10^6$.\n\n## Output\n\nFor each test case, output one line containing \"_Case #x: y_\", where _x_ is the test case number (starting from 1) and _y_ is the maximum happiness of the string that can be achieved by concatenating the pieces.\n\n[samples]\n\n## Note\n\nFor the first sample, the new string can be concatenated as _SADSAD_, hence the happiness is 2.For the second sample, the new string can be concatenated as _SSADD_, hence the happiness is 1.For the third sample, the new string can be concatenated as _SA+DS+ADSA+D_ = _SADSADSAD_, hence the happiness is 3.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the number of string pieces.  \n- Let $ S_k = (s_{k,1}, s_{k,2}, \\dots, s_{k,n_k}) $ be a sequence of strings, where each $ s_{k,i} \\in \\Sigma^* $, $ \\Sigma = \\{A, B, \\dots, Z\\} $, and $ 1 \\le |s_{k,i}| \\le 20 $.  \n\nLet $ \\text{happ}(w) $ denote the number of non-overlapping occurrences of the substring \"SAD\" in string $ w $.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 100 $  \n2. For each test case $ k $:  \n   - $ 1 \\le n_k \\le 2 \\times 10^5 $  \n   - $ \\sum_{k=1}^T n_k \\le 10^6 $  \n   - $ \\sum_{k=1}^T \\sum_{i=1}^{n_k} |s_{k,i}| \\le 2 \\times 10^6 $  \n\n**Objective**  \nFor each test case $ k $, find the permutation $ \\pi \\in \\text{Perm}(n_k) $ that maximizes:  \n$$\n\\text{happ}\\left( \\bigcup_{i=1}^{n_k} s_{k,\\pi(i)} \\right)\n$$  \nwhere $ \\bigcup_{i=1}^{n_k} s_{k,\\pi(i)} $ denotes the concatenation of the strings in order $ \\pi(1), \\pi(2), \\dots, \\pi(n_k) $.  \n\nOutput the maximum possible value of $ \\text{happ} $ over all permutations.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10243H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}