#include <bits/stdc++.h>
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
using namespace std;
int prng_base(const int l, const int r) {
  auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
  mt19937 mt_prng(seed);
  int base = uniform_int_distribution<int>(l + 1, r)(mt_prng);
  return base % 2 == 0 ? base - 1 : base;
}
struct RollingHash {
  static const int mod = (int)1e9 + 123;
  static vector<int> pow1;
  static vector<unsigned long long> pow2;
  static int base;
  static inline int diff(int a, int b) { return (a -= b) < 0 ? a + mod : a; }
  vector<int> pref1;
  vector<unsigned long long> pref2;
  RollingHash(const string &s)
      : pref1(s.size() + 1u, 0), pref2(s.size() + 1u, 0) {
    assert(base < mod);
    const int n = s.size();
    while ((int)pow1.size() <= n) {
      pow1.push_back(1LL * pow1.back() * base % mod);
      pow2.push_back(pow2.back() * base);
    }
    for (int i = 0; i < n; i++) {
      assert(base > s[i]);
      pref1[i + 1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;
      pref2[i + 1] = pref2[i] + s[i] * pow2[i];
    }
  }
  inline pair<int, unsigned long long> operator()(const int pos, const int len,
                                                  const int mxPow = 0) const {
    int hash1 = pref1[pos + len] - pref1[pos];
    unsigned long long hash2 = pref2[pos + len] - pref2[pos];
    if (hash1 < 0) hash1 += mod;
    if (mxPow != 0) {
      hash1 = 1LL * hash1 * pow1[mxPow - (pos + len - 1)] % mod;
      hash2 *= pow2[mxPow - (pos + len - 1)];
    }
    return make_pair(hash1, hash2);
  }
};
int RollingHash::base((int)1e9 + 7);
vector<int> RollingHash::pow1{1};
vector<unsigned long long> RollingHash::pow2{1};
map<pair<int, unsigned long long>, priority_queue<pair<int, int>>> ForwardHash;
map<pair<int, unsigned long long>, priority_queue<pair<int, int>>> ReverseHash;
map<pair<int, unsigned long long>, bool> isPalindrome;
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  RollingHash::base = prng_base(256, RollingHash::mod);
  int k, n;
  cin >> k >> n;
  string s[k];
  int b[k], isTaken[k];
  for (int idx = 0; idx < k; idx++) {
    cin >> s[idx] >> b[idx];
    RollingHash lH(s[idx]);
    auto hashStr = lH(0, n);
    reverse(s[idx].begin(), s[idx].end());
    RollingHash rH(s[idx]);
    auto hashRevStr = rH(0, n);
    ForwardHash[hashStr].push(make_pair(b[idx], idx));
    ReverseHash[hashRevStr].push(make_pair(b[idx], idx));
    if (hashStr == hashRevStr) isPalindrome[hashStr] = true;
    isTaken[idx] = 0;
  }
  int maxAtOdd = 0;
  long long ans = 0;
  for (auto hashPair : ForwardHash) {
    auto F = hashPair.second;
    auto R = ReverseHash[hashPair.first];
    while (1) {
      pair<int, int> u = make_pair(-1, -1), v = make_pair(-1, -1);
      while (!F.empty()) {
        if (!isTaken[F.top().second]) break;
        F.pop();
      }
      if (!F.empty()) {
        u = F.top();
        F.pop();
      }
      while (!R.empty()) {
        if (!isTaken[R.top().second] && R.top().second != u.second) break;
        R.pop();
      }
      if (!R.empty()) {
        v = R.top();
        R.pop();
      }
      if (u.second != -1 && v.second != -1 && u.first + v.first > 0) {
        ans += (u.first * 1ll + 1ll * v.first);
        isTaken[u.second] = 1;
        isTaken[v.second] = 1;
        if (isPalindrome[hashPair.first])
          maxAtOdd = max(maxAtOdd, max(-u.first, -v.first));
      } else {
        if (isPalindrome[hashPair.first])
          maxAtOdd = max(maxAtOdd, max(u.first, v.first));
        break;
      }
    }
  }
  cout << ans + maxAtOdd << "\n";
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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

### Response

```cpp
#include <bits/stdc++.h>
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
using namespace std;
int prng_base(const int l, const int r) {
  auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
  mt19937 mt_prng(seed);
  int base = uniform_int_distribution<int>(l + 1, r)(mt_prng);
  return base % 2 == 0 ? base - 1 : base;
}
struct RollingHash {
  static const int mod = (int)1e9 + 123;
  static vector<int> pow1;
  static vector<unsigned long long> pow2;
  static int base;
  static inline int diff(int a, int b) { return (a -= b) < 0 ? a + mod : a; }
  vector<int> pref1;
  vector<unsigned long long> pref2;
  RollingHash(const string &s)
      : pref1(s.size() + 1u, 0), pref2(s.size() + 1u, 0) {
    assert(base < mod);
    const int n = s.size();
    while ((int)pow1.size() <= n) {
      pow1.push_back(1LL * pow1.back() * base % mod);
      pow2.push_back(pow2.back() * base);
    }
    for (int i = 0; i < n; i++) {
      assert(base > s[i]);
      pref1[i + 1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;
      pref2[i + 1] = pref2[i] + s[i] * pow2[i];
    }
  }
  inline pair<int, unsigned long long> operator()(const int pos, const int len,
                                                  const int mxPow = 0) const {
    int hash1 = pref1[pos + len] - pref1[pos];
    unsigned long long hash2 = pref2[pos + len] - pref2[pos];
    if (hash1 < 0) hash1 += mod;
    if (mxPow != 0) {
      hash1 = 1LL * hash1 * pow1[mxPow - (pos + len - 1)] % mod;
      hash2 *= pow2[mxPow - (pos + len - 1)];
    }
    return make_pair(hash1, hash2);
  }
};
int RollingHash::base((int)1e9 + 7);
vector<int> RollingHash::pow1{1};
vector<unsigned long long> RollingHash::pow2{1};
map<pair<int, unsigned long long>, priority_queue<pair<int, int>>> ForwardHash;
map<pair<int, unsigned long long>, priority_queue<pair<int, int>>> ReverseHash;
map<pair<int, unsigned long long>, bool> isPalindrome;
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  RollingHash::base = prng_base(256, RollingHash::mod);
  int k, n;
  cin >> k >> n;
  string s[k];
  int b[k], isTaken[k];
  for (int idx = 0; idx < k; idx++) {
    cin >> s[idx] >> b[idx];
    RollingHash lH(s[idx]);
    auto hashStr = lH(0, n);
    reverse(s[idx].begin(), s[idx].end());
    RollingHash rH(s[idx]);
    auto hashRevStr = rH(0, n);
    ForwardHash[hashStr].push(make_pair(b[idx], idx));
    ReverseHash[hashRevStr].push(make_pair(b[idx], idx));
    if (hashStr == hashRevStr) isPalindrome[hashStr] = true;
    isTaken[idx] = 0;
  }
  int maxAtOdd = 0;
  long long ans = 0;
  for (auto hashPair : ForwardHash) {
    auto F = hashPair.second;
    auto R = ReverseHash[hashPair.first];
    while (1) {
      pair<int, int> u = make_pair(-1, -1), v = make_pair(-1, -1);
      while (!F.empty()) {
        if (!isTaken[F.top().second]) break;
        F.pop();
      }
      if (!F.empty()) {
        u = F.top();
        F.pop();
      }
      while (!R.empty()) {
        if (!isTaken[R.top().second] && R.top().second != u.second) break;
        R.pop();
      }
      if (!R.empty()) {
        v = R.top();
        R.pop();
      }
      if (u.second != -1 && v.second != -1 && u.first + v.first > 0) {
        ans += (u.first * 1ll + 1ll * v.first);
        isTaken[u.second] = 1;
        isTaken[v.second] = 1;
        if (isPalindrome[hashPair.first])
          maxAtOdd = max(maxAtOdd, max(-u.first, -v.first));
      } else {
        if (isPalindrome[hashPair.first])
          maxAtOdd = max(maxAtOdd, max(u.first, v.first));
        break;
      }
    }
  }
  cout << ans + maxAtOdd << "\n";
  return 0;
}

```