← 返回题目列表

Codeforces · 748/D

D. 圣诞老人和回文

中文机器翻译题面 查看原题

圣诞老人非常喜欢回文。最近是他的生日。他的 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。