对于一个非空字符串 S，如果将 S 中的所有字符颠倒输出后和原字符串相同，则称 S 为回文字符串。
例如，字符串 aba、abcba、abccba，都是回文字符串。但字符串 abc、abcb、abcdba，均不是回文串。
给定一个由 N 种不同的小写字母构成的长度为 L 的字符串 S。
S 可能不是回文串，允许对 S 进行编辑，直到 S 成为回文串，编辑方法有 2 种：
在 S 的任意位置增加一个小写字母 C，增加一个小写字母 C，需要付出的修改花费为 X_C。
删除 S 中的一个小写字母 C，删除一个小写字母 C，需要付出的删除花费为 Y_C。
请编程计算出，将 S 编辑为回文串的最小花费？
第 1 行读入两个整数 N 和 L。
第 2 行读入长度为 L 的字符串 S，S 中仅含小写字母。
接下来 N 行，每行读入一个小写字母 C，以及两个整数 X_C 和 Y_C，分别代表增加一个小写字母 C 和删除一个小写字母 C 所需的花费。
输出一个整数，代表将字符串 S 编辑为回文串的最小花费。
3 4 efgf e 50 80 f 30 60 g 10 65
50
2 6 bbbbcc b 700 300 c 800 8
16
10 50 ycymeqqybdqzqxdqcqqdqqqbdcbqcyqxybeyvyxemmeybvqvmq y 840 2360 q 6920 3770 e 6350 4330 z 2790 6465 d 2600 1725 b 4650 8535 x 6425 425 c 5770 4115 v 3845 7105 m 1700 2580
74075
如果在字符串的末尾插入 e，使其变为 efgfe，花费为 50。
如果删除字符串开头的 e，使其变为 fgf，花费为 80。
如果在字符串的开头插入 fgf ，使其变为 fgfefgf，花费为 30+10+30=70。
最小花费为 50。
对于 60\% 的数据，满足 1 \le N \le 10, 1\le L \le 10。
对于 100\% 的数据，满足 1 \le N \le 26, 1 \le L \le 2 \times 10^3, 0\le X_C,Y_C\le 10^4。