D. Santa Claus and a Palindrome

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. Santa 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_. Recall that a palindrome is a string that doesn't change after one reverses it. Since 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. ## Input 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). _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. ## Output In the only line print the required maximum possible beauty. [samples] ## Note In the first example Santa can obtain _abbaaaxyxaaabba_ by concatenating strings 5, 2, 7, 6 and 3 (in this order).