农民约翰通过一个自动化系统跟踪奶牛的位置。他在每头奶牛身上安装了一张电子身份标签，当奶牛经过扫描仪时，系统会读取该标签。每个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$