#100. 回文
回文
Description
约翰在每头牛身上都安装了一个标签电子身份标签,当牛通过扫描仪时,系统会读取这个标签。
每个 标签都是从 个小写字母的字母表中提取的长度为的字符串。
牛有时试图通过倒退来欺骗系统。
当一头牛的 标签是“”时,不管它朝哪个方向走,都会读到相同的 标签,而一头牛的标签是“”时,可能会被读到两个不同的 标签 和 。
约翰想修改牛的 标签,这样无论牛从哪个方向走过,都可以读到相同的内容。
例如,“”可以通过在末尾添加‘’,形成“”,这样的 标签就是回文向前和向后读取都是相同的内容。
将 标签更改为回文的其他方法包括将“”添加到开头,产生 标签“”;或删除字符‘’,产生 标签“”。
可以在字符串中的任何位置添加或删除字符,从而生成比原始字符串长或短的字符串。
给定牛的 标签及添加、删除每个字符的成本成本,求解使 标签满足回文字符串的最小成本。
一个空的 标签被认为已满足要求。
只有包含相关成本的字母才可以被添加到字符串中。
Format
Input
第 行包含两个整数 和 。
第 行包含个字符,表示初始的标签。
第 ..+ 行的每一行都包含一个字符和两个整数,分别表示添加和删除该字符的成本。
Output
单行输出更改给定标签为回文的最小成本。
Samples
3 4
abcb
a 1000 1100
b 350 700
c 200 800
900