题目描述

给定一个长度为$M$的字串$S$，字符串$S$由$N$个小写字母构成。现在想通过增加或删除字母将其变为回文串，增删特定字母花费不同，求最小花费。

输入格式

第$1$行：两个以空格分隔的整数：$N$和$M$  ($1 ≤ M ≤ 2,000,1 ≤ N ≤ 26$)

第$2$行：包含一个长度为$M$的字串$S$

第$3..N + 2$行：每行包含三个整数：一个字符和两个整数，两个整数分别是添加和删除该字符的花费。

输出格式

输出一个数表示最小花费。

样例

输入

3 4
abcb
a 1000 1100
b 350 700

输出

c 200 800

900

提示

样例解释：

如果在末尾插入“ $a$”以获得“ $abcba$”，则成本为1000。如果在开始时删除“ $a$”以获得“ $bcb$”，则成本为1100。如果插入“ $bcb$” 在字符串开始时，成本为350 + 200 + 350 = 900，这是最小值。