{"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":"CF752D"},"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"}],"meta":{"iden":"CF752D","tags":["data structures","greedy","hashing","strings"],"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"}}