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).
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jialin Ouyang (Jialin.Ouyang@gmail.com)
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    QuickScanner in = new QuickScanner(inputStream);
    QuickWriter out = new QuickWriter(outputStream);
    TaskD solver = new TaskD();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskD {
    int n;
    int m;
    char[] s;
    int[] a;
    long[] value;
    long[] hash;
    long[] revHash;
    int disHashCnt;
    long[] disHash;
    IntArrayList[] aLists;

    public void solve(int testNumber, QuickScanner in, QuickWriter out) {
      n = in.nextInt();
      m = in.nextInt();
      a = new int[n];
      hash = new long[n];
      revHash = new long[n];
      s = new char[m];
      value = new long[m];
      disHash = new long[n << 1];
      for (int i = 0; i < n; ++i) {
        in.next(s);
        a[i] = in.nextInt();
        for (int j = 0; j < m; ++j) {
          value[j] = s[j] - 'a';
        }
        hash[i] = HashUtils.calc(value);
        LongArrayUtils.reverse(value);
        revHash[i] = HashUtils.calc(value);
        disHash[i << 1] = hash[i];
        disHash[(i << 1) | 1] = revHash[i];
      }
      disHashCnt = LongArrayUtils.sortAndUnique(disHash);
      aLists = new IntArrayList[disHashCnt];
      for (int i = 0; i < disHashCnt; ++i) {
        aLists[i] = new IntArrayList();
      }
      for (int i = 0; i < n; ++i) {
        hash[i] = LongArrayUtils.lowerBound(disHash, 0, disHashCnt, hash[i]);
        revHash[i] = LongArrayUtils.lowerBound(disHash, 0, disHashCnt, revHash[i]);
        aLists[(int) hash[i]].add(a[i]);
      }
      for (int i = 0; i < disHashCnt; ++i) {
        Arrays.sort(aLists[i].values, 0, aLists[i].size());
      }
      out.println(calc());
    }

    int calc() {
      int res = 0, deltaRes = 0;
      for (int i = 0; i < n; ++i) {
        int idx = (int) hash[i], revIdx = (int) revHash[i];
        if (idx == revIdx) {
          while (!aLists[idx].isEmpty()) {
            IntArrayList lst = aLists[idx];
            int size = lst.size;
            if (lst.get(size - 1) <= 0) break;
            if (lst.size == 1) {
              deltaRes = Math.max(deltaRes, lst.get(size - 1));
              --lst.size;
              break;
            }
            int sum = lst.get(size - 1) + lst.get(size - 2);
            if (sum > 0) {
              res += sum;
              deltaRes = Math.max(deltaRes, -lst.get(size - 2));
              lst.size -= 2;
            } else {
              deltaRes = Math.max(deltaRes, lst.get(size - 1));
              --lst.size;
              break;
            }
          }
          continue;
        }
        while (!aLists[idx].isEmpty() && !aLists[revIdx].isEmpty()) {
          int sum = aLists[idx].get(aLists[idx].size - 1) + aLists[revIdx].get(aLists[revIdx].size - 1);
          if (sum > 0) {
            res += sum;
            --aLists[idx].size;
            --aLists[revIdx].size;
          } else {
            break;
          }
        }
      }
      return res + deltaRes;
    }

  }

  static class QuickScanner {
    private static final int BUFFER_SIZE = 1024;
    private InputStream stream;
    private byte[] buffer;
    private int currentPosition;
    private int numberOfChars;

    public QuickScanner(InputStream stream) {
      this.stream = stream;
      this.buffer = new byte[BUFFER_SIZE];
      this.currentPosition = 0;
      this.numberOfChars = 0;
    }

    public int next(char[] s) {
      return next(s, 0);
    }

    public int next(char[] s, int startIdx) {
      int b = nextNonSpaceChar();
      int res = 0;
      do {
        s[startIdx++] = (char) b;
        b = nextChar();
        ++res;
      } while (!isSpaceChar(b));
      return res;
    }

    public int nextInt() {
      int c = nextNonSpaceChar();
      boolean positive = true;
      if (c == '-') {
        positive = false;
        c = nextChar();
      }
      int res = 0;
      do {
        if (c < '0' || '9' < c) throw new RuntimeException();
        res = res * 10 + c - '0';
        c = nextChar();
      } while (!isSpaceChar(c));
      return positive ? res : -res;
    }

    public int nextNonSpaceChar() {
      int res = nextChar();
      for (; isSpaceChar(res) || res < 0; res = nextChar()) ;
      return res;
    }

    public int nextChar() {
      if (numberOfChars == -1) {
        throw new RuntimeException();
      }
      if (currentPosition >= numberOfChars) {
        currentPosition = 0;
        try {
          numberOfChars = stream.read(buffer);
        } catch (Exception e) {
          throw new RuntimeException(e);
        }
        if (numberOfChars <= 0) {
          return -1;
        }
      }
      return buffer[currentPosition++];
    }

    public boolean isSpaceChar(int c) {
      return c == ' ' || c == '\t' || isEndOfLineChar(c);
    }

    public boolean isEndOfLineChar(int c) {
      return c == '\n' || c == '\r' || c < 0;
    }

  }

  static interface IntCollection {
    int size();

    default boolean isEmpty() {
      return size() == 0;
    }

  }

  static class QuickWriter {
    private final PrintWriter writer;

    public QuickWriter(OutputStream outputStream) {
      this.writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public QuickWriter(Writer writer) {
      this.writer = new PrintWriter(writer);
    }

    public void print(Object... objects) {
      for (int i = 0; i < objects.length; ++i) {
        if (i > 0) {
          writer.print(' ');
        }
        writer.print(objects[i]);
      }
    }

    public void println(Object... objects) {
      print(objects);
      writer.print('\n');
    }

    public void close() {
      writer.close();
    }

  }

  static class HashUtils {
    public static long START_SEED = 100000000000000003L;
    public static long END_SEED = 1000000000000000003L;
    public static int BASE = 1000000007;

    public static long calc(long[] values) {
      return calc(values, 0, values.length);
    }

    public static long calc(long[] values, int fromIdx, int toIdx) {
      long res = START_SEED;
      for (int i = fromIdx; i < toIdx; ++i) {
        res = (i == fromIdx ? res : res * BASE) ^ hashSingle(values[i]);
      }
      return res * END_SEED;
    }

    private static long hashSingle(long value) {
      return (START_SEED ^ value) * END_SEED;
    }

  }

  static class IntArrayList implements IntCollection {
    private static int[] EMPTY = {};
    public int[] values;
    public int size;

    public IntArrayList() {
      values = EMPTY;
      clear();
    }

    public IntArrayList(int capacity) {
      values = new int[Integer.highestOneBit(capacity) << 1];
      clear();
    }


    public void clear() {
      size = 0;
    }


    public int size() {
      return size;
    }


    public void add(int value) {
      ensureCapacity(size() + 1);
      values[size++] = value;
    }

    public int get(int idx) {
      if (idx >= size) throw new ArrayIndexOutOfBoundsException();
      return values[idx];
    }


    public String toString() {
      StringBuilder sb = new StringBuilder("[");
      for (int i = 0; i < size(); ++i) {
        if (i > 0) sb.append(',');
        sb.append(values[i]);
      }
      return sb.append(']').toString();
    }

    protected void ensureCapacity(int capacity) {
      if (capacity < values.length) return;
      int[] newValues = new int[Integer.highestOneBit(capacity) << 1];
      for (int i = 0; i < values.length; ++i) {
        newValues[i] = values[i];
      }
      size = size();
      values = newValues;
    }

  }

  static class LongArrayUtils {
    public static void reverse(long[] values) {
      reverse(values, 0, values.length);
    }

    public static void reverse(long[] values, int fromIdx, int toIdx) {
      for (int i = fromIdx, j = toIdx - 1; i < j; ++i, --j) {
        values[i] ^= values[j];
        values[j] ^= values[i];
        values[i] ^= values[j];
      }
    }

    public static int unique(long[] values, int fromIdx, int toIdx) {
      if (fromIdx == toIdx) return 0;
      int res = 1;
      for (int i = fromIdx + 1; i < toIdx; ++i) {
        if (values[i - 1] != values[i]) {
          values[fromIdx + res++] = values[i];
        }
      }
      return res;
    }

    public static int sortAndUnique(long[] values) {
      return sortAndUnique(values, 0, values.length);
    }

    public static int sortAndUnique(long[] values, int fromIdx, int toIdx) {
      Arrays.sort(values, fromIdx, toIdx);
      return unique(values, fromIdx, toIdx);
    }

    public static int lowerBound(long[] values, int fromIdx, int toIdx, long value) {
      int res = fromIdx - 1;
      for (int lower = fromIdx, upper = toIdx - 1; lower <= upper; ) {
        int medium = (lower + upper) >> 1;
        if (values[medium] < value) {
          res = medium;
          lower = medium + 1;
        } else {
          upper = medium - 1;
        }
      }
      return res + 1;
//    int res = toIdx;
//    for (int lower = fromIdx, upper = toIdx - 1; lower <= upper; ) {
//      int medium = (lower + upper) >> 1;
//      if (value <= values[medium]) {
//        res = medium;
//        upper = medium - 1;
//      } else {
//        lower = medium + 1;
//      }
//    }
//    return res;
    }

  }
}

