CF748D Santa Claus and a Palindrome

圣诞老人非常喜欢回文串。最近是他的生日，他有 $k$ 个朋友来祝贺他，每位朋友都送给他一个长度为 $n$ 的字符串 $s_{i}$。我们用 $a_{i}$ 表示第 $i$ 个字符串的美丽值，$a_{i}$ 可能是负数——这意味着圣诞老人一点也不觉得这个字符串美丽。 圣诞老人痴迷于回文串。他一直在思考这样一个问题：通过连接他所拥有的一些（可能是全部）字符串（每个礼物最多只能使用一次），能够获得的回文串的最大可能总美丽值是多少？请注意，所有字符串的长度均为 $n$。 回文串是指反转后与原字符串相同的字符串。 由于空串也是回文串，因此答案不能为负。即使所有 $a_{i}$ 都是负数，圣诞老人仍然可以获得空串。

第一行包含两个正整数 $k$ 和 $n$，表示圣诞老人的朋友数量和他们送的每个字符串的长度（$1 \leq k, n \leq 100000$，且 $n \cdot k \leq 100000$）。 接下来的 $k$ 行，每行包含一个长度为 $n$ 的仅由小写英文字母组成的字符串 $s_{i}$ 及其美丽值 $a_{i}$（$-10000 \leq a_{i} \leq 10000$）。有些字符串可能会重复，而且相同的字符串可能有不同的美丽值。

输出一个整数，表示所能获得的最大可能总美丽值。

在第一个样例中，可以依次连接第 $5$、$2$、$7$、$6$、$3$ 个字符串（顺序为 abbaaaxyxaaabba），得到最大美丽值。 由 ChatGPT 5 翻译