圣诞老人非常喜欢回文。最近是他的生日。他的 k 个朋友来向他表示祝贺,每个人都送给他一根长度为 n 的绳子 si 。我们用 ai 表示第 i 根弦的美度。 ai 可能是负数——这意味着圣诞老人根本不觉得这个字符串漂亮。
圣诞老人对回文数很着迷。他正在思考以下问题:通过连接他拥有的一些(可能是全部)字符串可以获得回文的最大可能总美度是多少?每份礼物最多可使用一次。请注意,所有字符串都具有相同的长度 n。
回想一下,回文是一个在反转后不会改变的字符串。
由于空字符串也是回文,所以答案不能为负。即使所有的ai都是负数,圣诞老人也可以获得空字符串。
输入
第一行包含两个正整数 k 和 n 除以空格,分别表示圣诞老人朋友的数量和他们呈现的每个字符串的长度(1 ≤ k,n ≤ 100 000;n·k ≤ 100 000)。
k 线如下。其中第 i 个包含字符串 si 及其美丽值 ai (- 10 000 ≤ ai ≤ 10 000)。字符串由n个小写英文字母组成,它的美在于整数。有些字符串可能重合。而且,同样的琴弦也可以有不同的美感。
输出
在唯一的行中打印所需的最大可能的美感。
示例
输入 #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
注意
在第一个示例中,圣诞老人可以通过连接字符串 5、2、7、6 和 3(按此顺序)获得 abbaaaxyxaaabba。