题目描述

字串S长M，由N个小写字母构成。欲通过增删字母将其变为回文串

可以在任意位置删除或插入一些字符使字符串变成回文串

增删特定字母花费不同，求最小花费。

输入格式

第一行给两个数，n，m

第二行给一个m个字符组成的字符串

剩下n行，每行给一个字符c，两个整数a，d

a代表增加这个字符的花费，d代表删除这个字符的花费

(1 ≤ M ≤ 2,000)

N (1 ≤ N ≤ 26)

输出格式

输出一个整数，代表最小花费

样例 #1

样例输入 #1

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

样例输出 #1

900

提示

在字符串前面插入 "bcb" ，即可构成一个回文串，花费为350 + 200 + 350 = 900

记得开long long