A10717 | Santa Claus and a Palindrome

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<=100000$ ; $n·k <=100000$ ).

$k$ lines follow. The $i$ -th of them contains the string $s_{i}$ and its beauty $a_{i}$ ( $-10000<=a_{i}<=10000$ ). 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 only line print the required maximum possible beauty.

In the first example Santa can obtain abbaaaxyxaaabba by concatenating strings $5$ , $2$ , $7$ , $6$ and $3$ (in this order).