### 问题描述 小明喜欢回文字符串，现在他有 $k$ 个字符串 $s_i$，每个字符串的长度都是 $n$，我们用 $v_i$ 来表示小明对一个字符串的喜爱程度。 小明现在通过连接一些字符串（可能是全部），连接后得到的最终字符串必须是**回文的**，每个字符串最多使用一次。 我们定义 $S$ 为连接后的最终字符串，用 $w(S)$ 来表示小明对 $S$ 的喜爱程度，其定义为：如果 $S$ 使用了字符串 $s_i$，那么 $w(S) += v_i$。 请你求出 $w(S)$ 的最大值。 ### 输入格式 第一行，输入两个正整数 $k,n$，表示字符串的数量和每个字符串的长度。 随后 $k$ 行，每行输入一个字符串 $s_i$ 和其喜爱程度 $v_i$，用空格隔开（相同的字符串可能有不同的喜爱度）。 ### 输出格式 先输出`maximum favorability:`，然后输出 $w(S)$ 的最大值。 ### 样例输入 ```text 10 10 njxbzflaka -1 felbvvtkja 6 gxiuztqkcw 5 aomvscmtti 6 jsqmkoyuca -2 wckqtzuixg 5 ajktvvblef -5 ittmcsvmoa -1 akalfzbxjn 10 acuyokmqsj 8 ``` ### 样例输出 ```text maximum favorability:31 ``` ### 评测数据规模 对于所有评测数据，$1 \leq k,n \leq 10^5,n \times k \leq 10^5,-9999 \leq v_i \leq 9999$。