农民约翰通过一个自动化系统跟踪奶牛的位置。他在每头奶牛身上安装了一张电子身份标签，当奶牛经过扫描仪时，系统会读取该标签。每个ID标签的内容目前都是一个长度为M（1≤M≤2000）个字符的字符串，这些字符保证都是小写字符。

奶牛是淘气的动物，有时会试图通过倒退来欺骗扫描仪。约翰想调整奶牛的ID标签使得每个标签都是一个回文串，这样无论奶牛走哪个方向，它们的读数都是一样的。

给定一个由 n 个不同的小写字母构成的长 m 的字符串 s。可以通过在 \bm{s} 的任意位置增减字母将 s 改为回文串。增减字母的花费不同，求最小花费。

第 1 行是两个整数 n,m。

第 2 行是字符串 s。

接下 n 行，每行一个字符 c 和两个整数 x,y，表示添加一个 c 的花费为 x，删除一个 c 的花费为 y。

只有一个数字，表示最小花费。

对于 100\% 的数据，1\le m\le2\times10^3,1\le n\le 26,0\le x,y\le 10^4。

样例解释：如果在字符串最后添加一个字符'a'，那么花费是1000。如果删除开头的字符'a'则花费的更多。最便宜的方案是在字符串的开头添加三个字符"bcb"，花费为350 × 2 +200 =900

USCAO