预备知识

回文串是一个正读和反读都一样的字符串。例如，"level" 和 "noon" 就是回文串。特殊地，空字符串也是回文串。

题目描述

一个长度为 N 的字符串，全部由英文小写字母构成，共包含 K 种不同的字母。

现在想让该字符串变成回文串。

你可以在字符串的任意位置添加或删除任意一个字母。如果添加字母，你只能添加已有的 K 种字母之一。

添加或删除字母是需要代价的。

给出你 K 种字母的添加和删除代价，问：如何操作，可以使字符串变成回文串的总代价最小？你只需要输出最小总代价。

当然，空字符串也是回文串。

输入

第一行：两个整数 K, N

第二行：一个长度为 N 的字符串

接下来 K 行，对于字符串中的 K 种不同字母进行描述，每行描述一种字母：首先是一个字母（记为 C），接下来是两个整数 X, Y, 分别表示添加字母 C 的代价为 X，删除字母 C 的代价为 Y

输出

一个整数, 表示最小代价

输入样例

3 4
xyzy
x 1000 2000
y 200 1000
z 1000 100

输出样例

500

样例解释

一种可能的操作方案为：

删除字母 z 代价为 100，在前面添加 yy 代价为 400，共计 500.

还可能有其他的操作方案，但不存在代价比 500 更小的操作方案。

数据范围

1 ≤ K ≤ 26, 1 ≤ N ≤ 2000, 0 ≤ X, Y ≤ 10000