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*<sub class="lower-index">*i*</sub> having the same length *n*. We denote the beauty of the *i*-th string by *a*<sub class="lower-index">*i*</sub>. It can happen that *a*<sub class="lower-index">*i*</sub> 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*<sub class="lower-index">*i*</sub>'s are negative, Santa can obtain the empty string.
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*<sub class="lower-index">*i*</sub> and its beauty *a*<sub class="lower-index">*i*</sub> ( - 10 000 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 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.
In the first example Santa can obtain abbaaaxyxaaabba by concatenating strings 5, 2, 7, 6 and 3 (in this order).
7 3
abb 2
aaa -3
bba -1
zyz -4
abb 5
aaa 7
xyx 4
12
3 1
a 1
a 2
a 3
6
2 5
abcde 10000
abcde 10000
0
10 10
njxbzflaka -1
felbvvtkja 6
gxiuztqkcw 5
aomvscmtti 6
jsqmkoyuca -2
wckqtzuixg 5
ajktvvblef -5
ittmcsvmoa -1
akalfzbxjn 10
acuyokmqsj 8
31
10 20
jvyxocgomfmrtllgmagp 13
gvtjnyaofrswcnnifzfq 17
qisxpseggpjfoijmqnel -5
lenqmjiofjpggespxsiq 14
qfzfinncwsrfoaynjtvg 14
caayidazlylxyisihdhx 14
pgamglltrmfmogcoxyvj 11
xhdhisiyxlylzadiyaac 2
tbirihfpjgbbtclpxwhv 19
vhwxplctbbgjpfhiribt 10
109
1 1
e -1
0
2 1
t 1
t 2
3
1 2
yy 1
1
2 2
sn 1
ns 2
3
3 3
ada -1
xuv -1
vux 3
2
4 3
dbd 24
aba 90
cbc 54
aba 46
190
2 3
aaa 5
aaa -2
5
4 3
aba 4
aba 3
aba 3
aba -2
10
4 3
aba 4
aba 2
aba 2
aba -1
8
3 2
aa 5
aa -2
bb 1
5
2 2
aa 500
aa -50
500
2 1
a 5
a -1
5
2 3
aba 10
aba -3
10
2 3
aba 10
aba -9
10
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
    def insert(self, value):
        if self.value:
            if value < self.value:
                if self.left is None:
                    self.left = Node(value)
                else:
                    self.left.insert(value)
            else:
                if self.right is None:
                    self.right = Node(value)
                else:
                    self.right.insert(value)
        else:
            self.value = value
    def getLen(self):
        l = 1
        if self.left:
            l += self.left.getLen()
        if self.right:
            l += self.right.getLen()
        return l
    def getSum(self):
        s = self.value
        if self.left:
            s += self.left.getSum()
        if self.right:
            s += self.right.getSum()
        return s
    def getMax(self):
        mx = self.value
        if self.right:
            mx = self.right.getMax()
        return mx
    def getMin(self):
        mn = self.value
        if self.left:
            mn = self.left.getMin()
        return mn

    def getTree(self):
        ll = []
        lr = []
        if self.left:
            ll = self.left.getTree()
        if self.right:
            lr= self.right.getTree()
        return ll + [self.value] + lr

    def printTree(self):
        if self.left:
            self.left.printTree()
        with open('a_print_tree.txt', 'w') as f:
            print(self.value, end=" ", file=f)
        if self.right:
            self.right.printTree()

def deleteMax(root):
    if not root:
        return root
    if root.right:
        root.right = deleteMax(root.right)
    else:
        if root.left:
            return root.left      
    if root.left is None and root.right is None:
        return None
    return root

def deleteMin(root):
    if not root:
        return root
    if root.left:
        root.left = deleteMin(root.left)
    else:
        if root.right:
            return root.right      
    if root.left is None and root.right is None:
        return None
    return root


kn = input().split()
k = int(kn[0])
n = int(kn[1])
 
d = {}
d_pos = {}
d_neg = {}
total_sum = 0

def is_palindrome(s):
    if len(s) == 1:
        return True
    pal = True
    n = len(s)
    for i in range(n//2):
        if s[i] != s[n-1-i]:
            pal = False
            break
    return pal
 
def reverse_string(s):
    if len(s) == 1:
        return s
    new_s = ''
    for i in range(len(s)-1, -1, -1):
        new_s += s[i]
    return new_s

 
for i in range(k):
    sa = input().split()
    s = sa[0]
    a = int(sa[1])
    try:
        if d[s] is not None:
            d[s].insert(a)
            if a > 0:
                try:
                    if d_pos[s] is not None:
                        d_pos[s].insert(a)
                except KeyError:
                    d_pos[s] = Node(a)
            else:
                try:
                    if d_neg[s] is not None:
                        d_neg[s].insert(a)
                except KeyError:
                    d_neg[s] = Node(a)
    except KeyError:
        d[s] = Node(a)
        if a > 0:
            d_pos[s] = Node(a)
        else:
            d_neg[s] = Node(a)
 
keys_to_skip = []
solo_pal_max = 0

for key, val in d.items():
    if key in keys_to_skip:
        continue

    if is_palindrome(key):
        if d[key].getLen() > 1:
            try:
                if d_pos[key]:
                    neg_len = 0
                    pos_len = d_pos[key].getLen()
                    pos_min = d_pos[key].getMin()
                    pos_sum = d_pos[key].getSum()

                    try:
                        if d_neg[key]: 
                            neg_max = d_neg[key].getMax()
                            pos_neg_sum = neg_max + pos_min
                            neg_len = d_neg[key].getLen()
                        pos_neg_len_diff = d[key].getLen() - neg_len
                        if pos_neg_len_diff % 2 != 0:
                            if pos_neg_sum > 0:
                                total_sum += neg_max + pos_sum
                            else:
                                total_sum += (pos_sum - pos_min)
                        else:
                            total_sum += pos_sum
                    except KeyError:
                        if pos_len % 2 == 0:
                            total_sum += pos_sum
                        else:
                            total_sum += (pos_sum - pos_min)
                            if d[key].getMin() > solo_pal_max:
                                solo_pal_max = d[key].getMin()
                        pass
            except KeyError:
                pass
        else:
            if d[key].getMin() > solo_pal_max:
                solo_pal_max = d[key].getMin()
    else:
        try:
            rev_key = reverse_string(key)
            while d[key] and d[rev_key]:
                if d[key].getLen() > 0 and d[rev_key].getLen() > 0:
                    last_two_sum = d[key].getMax() + d[rev_key].getMax()
                    if last_two_sum > 0:
                        total_sum += last_two_sum
                    else:
                        break
                    d[key] = deleteMax(d[key])
                    d[rev_key] = deleteMax(d[rev_key])
            keys_to_skip.append(rev_key)
        except KeyError:
            pass
 
print(total_sum + solo_pal_max)
