5991: 进阶7.4.1 回文

内存限制:512 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:17 解决:10

题目描述

给定一个长度为m(m<=2000)的小写字母字符串,在给定组成该字符串的n(n<=26)个字符的添加和删除费用,求使原字符串变为回文串的最小费用

输入

第一行n,m

第二行原字符串

接下来n行开头一个小写字母,然后两个数字分别表示添加和删除该字母的费用

输出

输出一个数字,表示最小费用

样例输入 复制

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

样例输出 复制

900