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.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Calendar;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.SortedSet;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * #
 * @author pttrung
 */
public class D_Round_389_Div2 {

    public static long MOD = 1000000007;

    public static void main(String[] args) throws FileNotFoundException {
        // PrintWriter out = new PrintWriter(new FileOutputStream(new File(
        // "output.txt")));
        PrintWriter out = new PrintWriter(System.out);
        Scanner in = new Scanner();
        int k = in.nextInt();
        int n = in.nextInt();
        HashMap<String, TreeSet<Entry>> map = new HashMap();
        Entry[] data = new Entry[k];
        for (int i = 0; i < k; i++) {
            String v = in.next();
            int b = in.nextInt();
            if (!map.containsKey(v)) {
                map.put(v, new TreeSet());
            }
            data[i] = new Entry(v, b, i);
            map.get(v).add(data[i]);
        }
        Arrays.sort(data);
        int mid = 0;
        int result = 0;
        for (Entry e : data) {
            if (e.b < 0) {
                break;
            }
            if (map.get(e.v).contains(e)) {
                StringBuilder builder = new StringBuilder(e.v);
                String re = builder.reverse().toString();
                map.get(e.v).remove(e);
                if (map.containsKey(re) && !map.get(re).isEmpty()) {
                    Entry other = map.get(re).first();
                    int max = 0;
                    if (e.b + other.b >= 0) {
                        result += e.b + other.b;
                        max = e.b + other.b;
                        map.get(other.v).remove(other);
                    }

                    if (isPalind(e.v)) {
                        mid = Integer.max(mid, e.b - max);
                    }
                } else if (isPalind(e.v)) {
                    mid = Integer.max(mid, e.b);
                }
            }
            // System.out.println(e + "  " + result + " " + map);
        }
        out.println(result + mid);
        out.close();
    }

    static boolean isPalind(String v) {
        int n = v.length();
        for (int i = 0; i < n / 2; i++) {
            if (v.charAt(i) != v.charAt(n - i - 1)) {
                return false;
            }
        }
        return true;
    }

    static class Entry implements Comparable<Entry> {

        String v;
        int b, index;

        public Entry(String v, int b, int index) {
            this.v = v;
            this.b = b;
            this.index = index;
        }

        @Override
        public String toString() {
            return "Entry{" + "v=" + v + ", b=" + b + ", index=" + index + '}';
        }

        @Override
        public int compareTo(Entry o) {
            if (b != o.b) {
                return Integer.compare(o.b, b);
            }
            return Integer.compare(index, o.index);
        }

    }

    public static int[] KMP(String val) {
        int i = 0;
        int j = -1;
        int[] result = new int[val.length() + 1];
        result[0] = -1;
        while (i < val.length()) {
            while (j >= 0 && val.charAt(j) != val.charAt(i)) {
                j = result[j];
            }
            j++;
            i++;
            result[i] = j;
        }
        return result;

    }

    public static boolean nextPer(int[] data) {
        int i = data.length - 1;
        while (i > 0 && data[i] < data[i - 1]) {
            i--;
        }
        if (i == 0) {
            return false;
        }
        int j = data.length - 1;
        while (data[j] < data[i - 1]) {
            j--;
        }
        int temp = data[i - 1];
        data[i - 1] = data[j];
        data[j] = temp;
        Arrays.sort(data, i, data.length);
        return true;
    }

    public static int digit(long n) {
        int result = 0;
        while (n > 0) {
            n /= 10;
            result++;
        }
        return result;
    }

    public static double dist(long a, long b, long x, long y) {
        double val = (b - a) * (b - a) + (x - y) * (x - y);
        val = Math.sqrt(val);
        double other = x * x + a * a;
        other = Math.sqrt(other);
        return val + other;

    }

    public static class Point implements Comparable<Point> {

        int x, y;

        public Point(int start, int end) {
            this.x = start;
            this.y = end;
        }

        @Override
        public int hashCode() {
            int hash = 5;
            hash = 47 * hash + this.x;
            hash = 47 * hash + this.y;
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Point other = (Point) obj;
            if (this.x != other.x) {
                return false;
            }
            if (this.y != other.y) {
                return false;
            }
            return true;
        }

        @Override
        public int compareTo(Point o) {
            return Integer.compare(x, o.x);
        }
    }

    public static class FT {

        long[] data;

        FT(int n) {
            data = new long[n];
        }

        public void update(int index, long value) {
            while (index < data.length) {
                data[index] += value;
                index += (index & (-index));
            }
        }

        public long get(int index) {
            long result = 0;
            while (index > 0) {
                result += data[index];
                index -= (index & (-index));
            }
            return result;

        }
    }

    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static long pow(long a, long b, long MOD) {
        if (b == 0) {
            return 1;
        }
        if (b == 1) {
            return a;
        }
        long val = pow(a, b / 2, MOD);
        if (b % 2 == 0) {
            return val * val % MOD;
        } else {
            return val * (val * a % MOD) % MOD;

        }
    }

    static class Scanner {

        BufferedReader br;
        StringTokenizer st;

        public Scanner() throws FileNotFoundException {
            // System.setOut(new PrintStream(new BufferedOutputStream(System.out), true));
            br = new BufferedReader(new InputStreamReader(System.in));
            //  br = new BufferedReader(new InputStreamReader(new FileInputStream(new File("input.txt"))));
        }

        public String next() {

            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            st = null;
            try {
                return br.readLine();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }

        public boolean endLine() {
            try {
                String next = br.readLine();
                while (next != null && next.trim().isEmpty()) {
                    next = br.readLine();
                }
                if (next == null) {
                    return true;
                }
                st = new StringTokenizer(next);
                return st.hasMoreTokens();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }
    }
}
