{"problem":{"name":"D. Santa Claus and a Palindrome","description":{"content":"Santa Claus likes palindromes very much. There was his birthday recently. _k_ of his friends came to him to congratulate him, and each of them presented to him a string _s__i_ having the same length _","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF748D"},"statements":[{"statement_type":"Markdown","content":"Santa Claus likes palindromes very much. There was his birthday recently. _k_ of his friends came to him to congratulate him, and each of them presented to him a string _s__i_ having the same length _n_. We denote the beauty of the _i_\\-th string by _a__i_. It can happen that _a__i_ is negative — that means that Santa doesn't find this string beautiful at all.\n\nSanta Claus is crazy about palindromes. He is thinking about the following question: what is the maximum possible total beauty of a palindrome which can be obtained by concatenating some (possibly all) of the strings he has? Each present can be used at most once. Note that all strings have **the same length** _n_.\n\nRecall that a palindrome is a string that doesn't change after one reverses it.\n\nSince the empty string is a palindrome too, the answer can't be negative. Even if all _a__i_'s are negative, Santa can obtain the empty string.\n\n## Input\n\nThe first line contains two positive integers _k_ and _n_ divided by space and denoting the number of Santa friends and the length of every string they've presented, respectively (1 ≤ _k_, _n_ ≤ 100 000; _n_·_k_  ≤ 100 000).\n\n_k_ lines follow. The _i_\\-th of them contains the string _s__i_ and its beauty _a__i_ ( - 10 000 ≤ _a__i_ ≤ 10 000). The string consists of _n_ lowercase English letters, and its beauty is integer. Some of strings may coincide. Also, equal strings can have different beauties.\n\n## Output\n\nIn the only line print the required maximum possible beauty.\n\n[samples]\n\n## Note\n\nIn the first example Santa can obtain _abbaaaxyxaaabba_ by concatenating strings 5, 2, 7, 6 and 3 (in this order).","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Santa Claus 非常喜欢回文串。最近是他生日，有 #cf_span[k] 位朋友来祝贺他，每位朋友都送给他一个长度为 #cf_span[n] 的字符串 #cf_span[si]。我们用 #cf_span[ai] 表示第 #cf_span[i] 个字符串的美丽值。可能 #cf_span[ai] 为负数，这意味着 Santa 认为这个字符串并不美丽。\n\nSanta 对回文串着迷。他在思考这样一个问题：通过将他拥有的某些（可能全部）字符串拼接起来，能得到的回文串的最大总美丽值是多少？每个礼物最多只能使用一次。注意，所有字符串的长度都 *相同*，为 #cf_span[n]。\n\n回文串是指反转后不变的字符串。\n\n由于空字符串也是回文串，因此答案不可能为负数。即使所有 #cf_span[ai] 都为负数，Santa 仍然可以得到空字符串。\n\n第一行包含两个用空格分隔的正整数 #cf_span[k] 和 #cf_span[n]，分别表示 Santa 的朋友数量和每位朋友所赠字符串的长度（#cf_span[1 ≤ k, n ≤ 100 000]；#cf_span[n·k  ≤ 100 000]）。\n\n接下来 #cf_span[k] 行，第 #cf_span[i] 行包含字符串 #cf_span[si] 及其美丽值 #cf_span[ai]（#cf_span[ - 10 000 ≤ ai ≤ 10 000]）。字符串由 #cf_span[n] 个小写英文字母组成，美丽值为整数。某些字符串可能相同，且相同的字符串可能具有不同的美丽值。\n\n请在一行中输出所需的最大可能美丽值。\n\n在第一个例子中，Santa 可以通过按顺序拼接字符串 #cf_span[5]、#cf_span[2]、#cf_span[7]、#cf_span[6] 和 #cf_span[3] 得到 _abbaaaxyxaaabba_。\n\n## Input\n\n第一行包含两个用空格分隔的正整数 #cf_span[k] 和 #cf_span[n]，分别表示 Santa 的朋友数量和每位朋友所赠字符串的长度（#cf_span[1 ≤ k, n ≤ 100 000]；#cf_span[n·k  ≤ 100 000]）。#cf_span[k] 行 follow。第 #cf_span[i] 行包含字符串 #cf_span[si] 及其美丽值 #cf_span[ai]（#cf_span[ - 10 000 ≤ ai ≤ 10 000]）。字符串由 #cf_span[n] 个小写英文字母组成，美丽值为整数。某些字符串可能相同，且相同的字符串可能具有不同的美丽值。\n\n## Output\n\n请在一行中输出所需的最大可能美丽值。\n\n[samples]\n\n## Note\n\n在第一个例子中，Santa 可以通过按顺序拼接字符串 #cf_span[5]、#cf_span[2]、#cf_span[7]、#cf_span[6] 和 #cf_span[3] 得到 _abbaaaxyxaaabba_。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ k, n \\in \\mathbb{Z}^+ $ denote the number of strings and their fixed length, respectively.  \nLet $ S = \\{ (s_i, a_i) \\mid i \\in \\{1, \\dots, k\\} \\} $ be the set of string-beauty pairs, where $ s_i \\in \\Sigma^n $ (string of length $ n $ over lowercase English letters) and $ a_i \\in \\mathbb{Z} $ is its beauty.\n\n**Constraints**  \n1. $ 1 \\le k, n \\le 100{,}000 $  \n2. $ n \\cdot k \\le 100{,}000 $  \n3. $ -10{,}000 \\le a_i \\le 10{,}000 $\n\n**Objective**  \nSelect a subset $ T \\subseteq S $ such that the concatenation $ \\bigoplus_{(s,a) \\in T} s $ forms a palindrome, and maximize the total beauty $ \\sum_{(s,a) \\in T} a $.  \n\nThe empty concatenation is allowed (beauty = 0).\n\n**Key Insight**  \nSince all strings have the same length $ n $, for the concatenation of strings to be a palindrome, the multiset of selected strings must be arrangeable such that the sequence reads the same forwards and backwards. This requires:  \n- For each string $ s $, either:  \n  (a) $ s $ is itself a palindrome, and can be placed in the center (at most one such string can be used centrally), or  \n  (b) there exists a matching string $ s' $ such that $ s' = \\text{reverse}(s) $, and they are used symmetrically (in pairs).  \n\nDefine:  \n- Let $ P $ be the set of palindromic strings in $ S $.  \n- Let $ R $ be the set of non-palindromic strings, grouped into unordered pairs $ \\{s, \\text{reverse}(s)\\} $ where $ s \\ne \\text{reverse}(s) $.  \n\nFor each such pair $ \\{s, \\text{reverse}(s)\\} $, we can select any number of matching pairs $ (s, \\text{reverse}(s)) $, and the optimal choice is to take all pairs with non-negative total beauty (i.e., sum of beauties of both strings).  \nFor palindromic strings, we may use any even number of them in symmetric pairs (like non-palindromic), and optionally use one unpaired palindromic string in the center — we choose the one with maximum beauty among those with non-negative contribution (or skip if all are negative).\n\n**Formal Objective**  \nMaximize:  \n$$\n\\max \\left( 0,\\ \\max_{\\substack{T \\subseteq S \\\\ \\text{concat}(T) \\text{ is palindrome}}} \\sum_{(s,a) \\in T} a \\right)\n$$\n\n**Computationally:**  \n- Group strings by their reverse equivalence class.  \n- For each pair $ \\{s, r(s)\\} $ with $ s \\ne r(s) $:  \n  Let $ M = \\max \\left(0, \\sum_{(s,a) \\in \\text{group}} a + \\sum_{(r(s),b) \\in \\text{group}} b \\right) $, and accumulate the maximum possible sum from pairing.  \n- For palindromic strings:  \n  Let $ B = \\{ a \\mid (s,a) \\in S, s = \\text{reverse}(s) \\} $.  \n  Let $ \\text{pair\\_sum} = \\sum_{\\text{even number of palindromes}} \\text{sum of pairs with non-negative total} $.  \n  Let $ \\text{center\\_max} = \\max( \\{0\\} \\cup \\{ a \\in B \\mid a > 0 \\} ) $.  \n- Total = pair_sum + center_max.\n\n**Final Output**  \nThe maximum total beauty achievable by any palindromic concatenation (including empty).","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF748D","tags":["constructive algorithms","data structures","greedy"],"sample_group":[["7 3\nabb 2\naaa -3\nbba -1\nzyz -4\nabb 5\naaa 7\nxyx 4","12"],["3 1\na 1\na 2\na 3","6"],["2 5\nabcde 10000\nabcde 10000","0"]],"created_at":"2026-03-03 11:00:39"}}