题目描述

如果一个字符串从左向右读和从右向左读完全相同，则称它为回文串。

给定一个长度为 $L$、只包含小写英文字母的字符串 $S$。你可以进行以下操作：

• 在字符串的任意位置插入一个字母 $C$，花费为 $X_C$；
• 删除字符串中的一个字母 $C$，花费为 $Y_C$。

求将 $S$ 变成回文串所需的最小总花费。

输入格式

第一行包含两个整数 $N,L$，表示给出操作费用的字母种数和字符串长度。

第二行包含一个长度为 $L$ 的字符串 $S$。

接下来 $N$ 行，每行包含一个小写英文字母 $C$ 和两个整数 $X_C,Y_C$，分别表示插入和删除字母 $C$ 的花费。

输出格式

输出一个整数，表示最小总花费。

3 4
efgf
e 50 80
f 30 60
g 10 65

50

数据范围与提示

• 对于 $60\%$ 的数据，$1 \le N,L \le 10$
• 对于全部数据，$1 \le N \le 26$，$1 \le L \le 2000$
• $0 \le X_C,Y_C \le 10^4$
• 字符串 $S$ 中出现的每个字母都有对应的操作费用