CF748D.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.

圣诞老人非常喜欢回文串。他最近刚刚过生日，有 $k$ 位朋友前来祝贺，并各自送给他一个长度均为 $n$ 的字符串 $s_i$。我们用 $a_i$ 表示第 $i$ 个字符串的“美观度”。需要注意的是，$a_i$ 可能为负数——这意味着圣诞老人完全不觉得该字符串美观。

圣诞老人对回文串痴迷至极。他正在思考如下问题：通过将他所收到的部分（或全部）字符串按一定顺序拼接起来，所能得到的回文串的最大总美观度是多少？每个礼物最多只能使用一次。注意：所有字符串长度均为 $n$。

回忆一下，回文串是指将其反转后仍保持不变的字符串。

由于空串本身也是回文串，因此答案不可能为负数。即使所有 $a_i$ 均为负数，圣诞老人仍可选择不使用任何字符串，从而得到空串。

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.

第一行包含两个正整数 $k$ 和 $n$，以空格分隔，分别表示圣诞老人朋友们的数量以及他们所提交的每个字符串的长度（$1 \le k,\,n \le 100\,000$；$n\cdot k  \le 100\,000$）。

接下来是 $k$ 行。其中第 $i$ 行包含字符串 $s_i$ 及其美丽值 $a_i$（$-10\,000 \le a_i \le 10\,000$）。该字符串由 $n$ 个小写英文字母组成，其美丽值为整数。某些字符串可能相同；此外，相同的字符串也可能具有不同的美丽值。

In the only line print the required maximum possible beauty.

在唯一的一行中输出所需的最大可能美观度。

In the first example Santa can obtain abbaaaxyxaaabba by concatenating strings 5, 2, 7, 6 and 3 (in this order).

在第一个例子中，圣诞老人可以通过按顺序拼接字符串 5、2、7、6 和 3 得到 abbaaaxyxaaabba。