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).
Santa Claus 非常喜欢回文串。最近是他生日，有 #cf_span[k] 位朋友来祝贺他，每位朋友都送给他一个长度为 #cf_span[n] 的字符串 #cf_span[si]。我们用 #cf_span[ai] 表示第 #cf_span[i] 个字符串的美丽值。可能 #cf_span[ai] 为负数，这意味着 Santa 认为这个字符串并不美丽。
Santa 对回文串着迷。他在思考这样一个问题：通过将他拥有的某些（可能全部）字符串拼接起来，能得到的回文串的最大总美丽值是多少？每个礼物最多只能使用一次。注意，所有字符串的长度都 *相同*，为 #cf_span[n]。
回文串是指反转后不变的字符串。
由于空字符串也是回文串，因此答案不可能为负数。即使所有 #cf_span[ai] 都为负数，Santa 仍然可以得到空字符串。
第一行包含两个用空格分隔的正整数 #cf_span[k] 和 #cf_span[n]，分别表示 Santa 的朋友数量和每位朋友所赠字符串的长度（#cf_span[1 ≤ k, n ≤ 100 000]；#cf_span[n·k ≤ 100 000]）。
接下来 #cf_span[k] 行，第 #cf_span[i] 行包含字符串 #cf_span[si] 及其美丽值 #cf_span[ai]（#cf_span[ - 10 000 ≤ ai ≤ 10 000]）。字符串由 #cf_span[n] 个小写英文字母组成，美丽值为整数。某些字符串可能相同，且相同的字符串可能具有不同的美丽值。
请在一行中输出所需的最大可能美丽值。
在第一个例子中，Santa 可以通过按顺序拼接字符串 #cf_span[5]、#cf_span[2]、#cf_span[7]、#cf_span[6] 和 #cf_span[3] 得到 _abbaaaxyxaaabba_。
## Input
第一行包含两个用空格分隔的正整数 #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] 个小写英文字母组成，美丽值为整数。某些字符串可能相同，且相同的字符串可能具有不同的美丽值。
## Output
请在一行中输出所需的最大可能美丽值。
[samples]
## Note
在第一个例子中，Santa 可以通过按顺序拼接字符串 #cf_span[5]、#cf_span[2]、#cf_span[7]、#cf_span[6] 和 #cf_span[3] 得到 _abbaaaxyxaaabba_。
**Definitions**
Let $ k, n \in \mathbb{Z}^+ $ denote the number of strings and their fixed length, respectively.
Let $ 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.
**Constraints**
1. $ 1 \le k, n \le 100{,}000 $
2. $ n \cdot k \le 100{,}000 $
3. $ -10{,}000 \le a_i \le 10{,}000 $
**Objective**
Select 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 $.
The empty concatenation is allowed (beauty = 0).
**Key Insight**
Since 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:
- For each string $ s $, either:
(a) $ s $ is itself a palindrome, and can be placed in the center (at most one such string can be used centrally), or
(b) there exists a matching string $ s' $ such that $ s' = \text{reverse}(s) $, and they are used symmetrically (in pairs).
Define:
- Let $ P $ be the set of palindromic strings in $ S $.
- Let $ R $ be the set of non-palindromic strings, grouped into unordered pairs $ \{s, \text{reverse}(s)\} $ where $ s \ne \text{reverse}(s) $.
For 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).
For 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).
**Formal Objective**
Maximize:
$$
\max \left( 0,\ \max_{\substack{T \subseteq S \\ \text{concat}(T) \text{ is palindrome}}} \sum_{(s,a) \in T} a \right)
$$
**Computationally:**
- Group strings by their reverse equivalence class.
- For each pair $ \{s, r(s)\} $ with $ s \ne r(s) $:
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.
- For palindromic strings:
Let $ B = \{ a \mid (s,a) \in S, s = \text{reverse}(s) \} $.
Let $ \text{pair\_sum} = \sum_{\text{even number of palindromes}} \text{sum of pairs with non-negative total} $.
Let $ \text{center\_max} = \max( \{0\} \cup \{ a \in B \mid a > 0 \} ) $.
- Total = pair_sum + center_max.
**Final Output**
The maximum total beauty achievable by any palindromic concatenation (including empty).