[Usaco2007 Open]Cheappal 廉价回文

为了跟踪所有奶牛，农夫 John 在农场中安装了一套自动识别系统。每头奶牛都有一个电子名字，当奶牛经过识别系统时，系统会自动读取它的名字。

每头奶牛的电子名字是一个长度为 $M$ 的字符串，其中只包含 $N$ 种不同的字母。

淘气的奶牛很快发现了系统的漏洞：它们可以倒着通过识别器。名字为 abcba 的奶牛不会造成问题，因为它的名字正读和反读相同；但名字为 abcb 的奶牛会被系统识别成两头不同的奶牛，名字分别为 abcb 和 bcba。

农夫 John 希望修改奶牛的名字，使其成为回文串，即正读和反读完全相同。例如，可以在 abcb 的末尾添加字母 a；也可以在开头添加字符串 bcb，得到 bcbabcb；还可以删除开头的字母 a，得到 bcb。

John 可以在名字的任意位置添加或删除字母。由于名字以电子形式存储，添加或删除每种字母都需要支付相应的费用。给定奶牛的初始名字，以及每种字母的添加费用和删除费用，请计算将名字修改为回文串所需的最小费用。

空字符串也被视为合法的回文名字。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $M$ ，分别表示字母种类数和初始名字的长度。

第二行包含一个长度为 $M$ 的字符串，表示奶牛的初始名字。

接下来 $N$ 行，每行包含一个字母和两个整数，分别表示添加该字母的费用和删除该字母的费用。

输出一个整数，表示将初始名字修改为回文串所需的最小费用。

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

本题为 USACO 2007 Open 试题「廉价回文」，题面与测试数据整理自 BZOJ。

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