做了很久不会写，请教大佬！

描述

小炫今天刚学完“字符串类型”这一节内容，学到了一个新的概念，回文字符串，大家都知道回文串的概念，一个字符串正向读和反向读是相同的，例如aba,abcba等等（空串也视为回文串），现在我们的任务是将一个字符串S变成回文串。我们可以通过删除某个字符或者添加某个字符的组合操作使它成为回文串，但是每个操作都有一个代价，现在我们希望花费最小的代价使这个字符串变为回文串。字符串都由小写字母组成。

输入描述

第一行为正整数t(≤10)，表示数据组数；

每组数据中： 第一行为两个正整数m(≤26), n(≤2000)，m表示变换规则的数目，n表示字符串的长度； 第二行为长度为n的字符串S；接下来m行为变换规则，每条规则一定是这样的形式：<字符ch> <添加此字符的代价> <删除此字符的代价>；字符串中的任一字符有且仅有一条对应的规则，添加代价和删除代价均为不超过3000的正整数。

输出描述

对于每组数据，输出使S串变成回文串花费的最小代价。

用例输入 1

1

3 4

abcb

a 1000 1100

b 350 700

c 200 800

用例输出 1

900

提示

在原串的左边添加bcb，代价是900，这是最小的代价。