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.
$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).
输入输出样例
输入 #1
7 3 abb 2 aaa -3 bba -1 zyz -4 abb 5 aaa 7 xyx 4
输出 #1
12
输入 #2
3 1 a 1 a 2 a 3
输出 #2
6
输入 #3
2 5 abcde 10000 abcde 10000
输出 #3
0
说明/提示
In the first example Santa can obtain abbaaaxyxaaabba by concatenating strings $5$ , $2$ , $7$ , $6$ and $3$ (in this order).