时间限制：1秒　　内存限制：256M

---

【问题描述】

　　电子ID是一个由小写字母组成的长度为 \(M\) 的字符串，字符串中出现的不同的字母有 \(N\) 种。由于最初设计的缺陷，正向扫描和反向扫描电子ID得到了不同信息。于是设计者想将其改造成回文串。

　　改造的方法可以通过删除或添加字符来实现，当然无论是删除还是添加，不同的字符都需要不同的代价。那么该怎样改造，才能使代价最少？

【输入格式】

　　第一行包含两个用空格分开的整数 \(N\) 和 \(M\)；
　　第二行包含一个长度为 \(M\) 的字符串，表示某头电子ID；
　　接下来的 \(N\) 行，每行包含三个用空格分开的数据，第一个是一个英文字母 \(ch\)，第二个是一个整数 \(C_1\)，表示在电子ID中插入一个 \(ch\) 的代价，第三个是一个整数 \(C_2\)，表示在电子ID删除一个字符 \(ch\) 的代价。

【输出格式】

　　一行包含一个整数，表示最小代价。

【输入输出样例】

　Input

3 4
yscs
y 1000 1100
s 350 700
c 200 800 

　Output

900

【输入输出样例解释】

　　如果我们在末尾插入一个“y”来获取“yscsy”，那么费用将是1000；
　　如果我们从头开始删除“y”来获取“scs”，那么费用将是1100；
　　如果我们在前面插入“scs”得到“scsyscs”，成本将是350+200+350=900，这是最小的。

【数据说明】

　　对于 \(100\%\) 的数据 \(1≤N≤26\)，\(1≤M≤2000\)，\(0≤C_1,C_2≤10000\)。

【来源】

　　Mr.he