{"raw_statement":[{"iden":"statement","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."},{"iden":"input","content":"The 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."},{"iden":"output","content":"In the only line print the required maximum possible beauty."},{"iden":"examples","content":"Input\n\n7 3\nabb 2\naaa -3\nbba -1\nzyz -4\nabb 5\naaa 7\nxyx 4\n\nOutput\n\n12\n\nInput\n\n3 1\na 1\na 2\na 3\n\nOutput\n\n6\n\nInput\n\n2 5\nabcde 10000\nabcde 10000\n\nOutput\n\n0"},{"iden":"note","content":"In the first example Santa can obtain _abbaaaxyxaaabba_ by concatenating strings 5, 2, 7, 6 and 3 (in this order)."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}