D. Санта-Клаус и палиндром
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Санта-Клаус очень любит палиндромы. Недавно у него был день рождения. В гости к Санта-Клаусу пришли k друзей, каждый из них подарил ему строку si одной и той же длины n, красота i-й строки равна ai. Возможно, что ai является отрицательным — это значит, что строка не является красивой по мнению Санта-Клауса.

Санта-Клаус без ума от палиндромов. Ему стало интересно: какую максимальную суммарную красоту может иметь палиндром, если склеить какие-то (возможно все) из подаренных строк? Каждый подарок можно использовать не более одного раза. Обратите внимание, что все подаренные строки имеют одинаковую длину n.

Напоминаем, что палиндром — это строка, которая не изменится, если её развернуть задом наперёд.

Так как пустая строка является палиндромом, то искомая максимальная красота — неотрицательна. Даже если все ai отрицательны, Санта-Клаус может получить пустую строку в качестве палиндрома.

Входные данные

В первой строке задано два целых числа через пробел, k и n — количество друзей Санта-Клауса и длина строки, подаренной каждым другом (1 ≤ k, n ≤ 100 000; n·k  ≤ 100 000).

Далее следуют k строк. i-я из них содержит подаренную строку si и её красоту ai ( - 10 000 ≤ ai ≤ 10 000). Строка состоит из n строчных букв латинского алфавита, а её красота — целое число. Подаренные строки могут совпадать. Одинаковые строки могут иметь разную красоту.

Выходные данные

Выведите искомую максимальную суммарную красоту.

Примеры
Входные данные
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
Примечание

В первом примере из условия Санта-Клаус может склеить палиндром abbaaaxyxaaabba, используя строки 5, 2, 7, 6, 3 (склеив их именно в этом порядке).