题目描述

对于一个非空字符串 $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

数据范围

对于 $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$。