3077 - 最小代价回文串
时间限制 : 1 秒
内存限制 : 128 MB
给定由k个字符组成的长度为n的字符串,任意增加或删除字符,将其变为回文串。增加、删除每个字符的代价不同。求最小代价。
输入
第一行为两个正整数n和k。 第2到k+1行每行为一个字母、两个正整数,表示k个字符的增加、删除代价。
输出
一个正整数,表示最小代价。
样例
输入
4 3 a 1000 1100 b 350 700 c 200 800
输出
900
来源
动规专题