5746. D - 小海狸的回文2
时间限制：1000 MS 内存限制：256 MB
题目描述
### D - 小海狸的回文2 时间限制: 2 s | 内存限制: 256 MB 小海狸有k 个字符串，长度均为n ，他用a_i 表示第i 个字符串的美感度。小海狸想要将他的一些（也可以是0或k 个）字符串连接成回文串，并且他希望连接成的字符串拥有最大美感度。注意：a_i 可能为负，这也表示小海狸认为字符串i 毫无美感。 ### 输入 第一行包含两个正整数k 和n ，分别表示字符串的数量和长度$（1 \leq k，n \leq 100000；n \cdot k \leq 100000 ）$。 接下来k 行包含字符串$s_i$ 及其美感度$a_i （-10000 \leq a_i \leq 10000 ）$。字符串由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 ``` ### 提示 - 子任务一：30分，满足$1 \leq k，n \leq 10；n \cdot k \leq 100 $； - 子任务二：30分，满足$1 \leq k，n \leq 1000；n \cdot k \leq 1000 $； - 子任务三：40分，满足$1 \leq k，n \leq 100000；n \cdot k \leq 100000 $。 在第一个示例中，可以通过连接字符串5、2、7、6和3（按此顺序）来获得“abbaaxyxaaabba”。