题目描述

约翰在每头牛身上都安装了一个$i$$d$标签$（$电子身份标签$）$，当牛通过扫描仪时，系统会读取这个标签。

每个$i$$d$标签都是从$n$$（$$1$$≤$$n$$≤$$2$$6$$）$个小写字母的字母表中提取的长度为$m$$（$$1$$≤$$m$$≤$$2$$0$$0$$0$$）$的字符串。

牛有时试图通过倒退来欺骗系统。

当一头牛的$i$$d$标签是“$a$$b$$c$$b$$a$”时，不管它朝哪个方向走，都会读到相同的$i$$d$标签，而一头牛的$i$$d$标签是“$a$$b$$c$$b$”时，可能会被读到两个不同的$i$$d$标签$（$$a$$b$$c$$b$和$b$$c$$b$$a$$）$。

约翰想修改牛的$i$$d$标签，这样无论牛从哪个方向走过，都可以读到相同的内容。

例如，“$a$$b$$c$$b$”可以通过在末尾添加‘$a$’，形成“$a$$b$$c$$b$$a$”，这样的$i$$d$标签就是回文$（$向前和向后读取都是相同的内容$）$。

将$i$$d$标签更改为回文的其他方法包括将“$b$$c$$b$”添加到开头，产生$i$$d$标签“$b$$c$$b$$a$$b$$c$$b$”；或删除字符‘$a$’，产生$i$$d$标签“$b$$c$$b$”。

可以在字符串中的任何位置添加或删除字符，从而生成比原始字符串长或短的字符串。

给定牛的$i$$d$标签及添加、删除每个字符的成本$（$$0$$≤$成本$≤$$1$$0$$0$$0$$0$$）$，求解使$i$$d$标签满足回文字符串的最小成本。

一个空的$i$$d$标签被认为已满足要求。

只有包含相关成本的字母才可以被添加到字符串中。

输入格式

第$1$行包含两个整数$n$和$m$。

第$2$行包含$m$个字符，表示初始的$i$$d$标签。

第$3$..$n$+$2$行的每一行都包含一个字符和两个整数，分别表示添加和删除该字符的成本。

输出格式

单行输出更改给定标签为回文的最小成本。

样例

3 4
abcb
a 1000 1100
b 350 700
c 200 800

900

来源

POJ3280