Description

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 si having the same length n. We denote the beauty of the i-th string by ai. It can happen that ai 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 ai'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 si and its beauty ai ( - 10 000 ≤ ai ≤ 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.

Examples

input
7 3
abb 2
aaa -3
bba -1
zyz -4
abb 5
aaa 7
xyx 4
output
12
input
3 1
a 1
a 2
a 3
output
6
input
2 5
abcde 10000
abcde 10000
output
0

Note

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

Key

给出若干等长字符串与其对应价值（可重复，重复的字符串价值可不同），从字符串中选出若干字符串，组成一个回文串，问最大价值多少。

一个字符串要被使用，就必须有对应的逆序字符串，比如要使用abb，就必须有对应的bba。先预处理将重复字符串的价值们放在数组里从大到小排列。对于abb、bba式的自身非回文的串很简单，只要两两价值相加大于零就选中（贪心）。

对于aba式的自身就是回文的，可以选择如上的成对出现，也可以选择放在正中间（然而最多只能有一个放在目标回文串的正中间，为了方便描述称其为“中间串”）。首先成对的处理，两两价值相加大于零就选中（贪心）。若该串重复的个数为奇数，可能有唯一落单的正价值，将其成为“中间串”候补。但还有个有问题，比如输入：

1
2
3

2 3
aba 5
aba -1

两者结合结果为4，大于0。但是此处只选择第一个更优。因而当成对串的第二个串为负时，第一个串也成为“中间串”候补。

以上两种成为“中间串”候补的情况，对于第一种情况：若选中，则总价值+=该串价值。对于第二种情况：若选中，则\(V_{总}-=V_{该串对应的负价值串}\)，即\(V_{总}+=-V_{该串对应的负价值串}\)。则找出最大的\(|V_{候补串}|\)或\(|V_{候补串对应的负价值串}|\)即可。若没有候补串就不要中间串了。

Code

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
using namespace std;
int k, n;
map<string, vector<int> > mp;

char sp[100000];
void pal(string s) {
	int idx = n;
	for (const auto& c : s) {
		sp[--idx] = c;
	}
	sp[n] = '\0';
}

bool cmp(int a, int b) {
	return a > b;
}

int main()
{
	cin >> k >> n;
	for (int i = 0; i < k; ++i) {
		string s;
		int v;
		cin >> s >> v;
		mp[s].push_back(v);
	}
	int res = 0;
	int mid = 0;
	for (auto &e : mp) {
		vector<int> &now = e.second;
		if (now.empty()) continue;
		sort(now.begin(), now.end(), cmp);
		pal(e.first);
		if (e.first == sp) {
			int l = now.size();
			int i;
			for (i = 0; i < l - 1; i += 2) {
				if (now[i] + now[i + 1] <= 0) break;
				res += now[i] + now[i + 1];
			}
			if (i && i-1<l && now[i - 1] < 0) {
				mid = max(-now[i - 1], mid);
			}
			else if(i<l) {
				mid = max(now[i],mid);
			}
		}
		else {
			vector<int> &nxt = mp[sp];
			sort(nxt.begin(), nxt.end(), cmp);
			int l = min(nxt.size(), now.size());
			for (int i = 0; i < l; ++i) {
				if (nxt[i] + now[i] <= 0) break;
				res += nxt[i] + now[i];
			}
			nxt.clear();
		}
	}
	cout << res + mid;
	return 0;
}

XieNaoban's Blog

Codeforces Round 389(Div. 2) - D. Santa Claus and a Palindrome