D. 一串简单的字符

给定一个长度为M的字符串（字符串由'a'~'z'组成），可以在任意位置删除或者插入一些字符使得原字符串变成回文串。例如'abcb'可以在最后添加一个'a'变成'abcba'回文串，或者删除最开始的'a'变成'bcb'回文串，又或者在最开头添加'bcb'变成'bcbabcb'回文串。

需要注意的是，不论是删除或者添加相关的字母都需要付出相应的代价t。请你找出把原来的字符串变成回文串的最小的费用。

PS. 空字符串也是一个回文串。

输入数据由若干行；

第一行为两个用空格分开的整数N、M分别代表给定的字符串中所包含的字母的种数和字符串的长度；

第二行为一个长度为M的字符串；

第三行到第N+2行，每行有一个用空格分隔的三元组，包含一个字符和两个整数，分别代表添加和删除这个字符的代价。

输出数据为一行一个整数，代表将给定的字符串变成回文串的最小代价。

数据规模：

对于100%的数据：

1\leq N\leq 26、

1\leq M\leq 2,000、

1\leq t\leq 10,000。