{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cp\u003eAP现在定义两个字符串操作。\u003cp\u003e\n \u003cp\u003e 操作1:在任意位置添加一个字符char(只有小写字母),并花费a[char-\u0027a\u0027]元\u003cp\u003e\n \u003cp\u003e 操作2:在任意位置删除一个字符char(只有小写字母),并花费b[char-\u0027a\u0027]元\u003cp\u003e\n 现在给你一个字符串S,问最少消耗多少花费使其变成回文串。\n \n \u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 第一行,两个整数由空格分开:N和M (1 ≤ M ≤ 2,000) (1 ≤ N ≤ 26)\n \u003cbr\u003e第二行,长度为M的字符串\n \u003cbr\u003e第三行开始到第N+2行,每行包括一个字母char和两个整数x, y。分别代表字母char添加和删除所需要的花费a[char-\u0027a\u0027] \u003d x, b[char-\u0027a\u0027] \u003d y. (x, y \u003c\u003d 1e4)\n \n \u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 单个整数的一行,最少消耗多少花费使其变成回文串。\n\n \u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e3 4\nabcb\na 1000 1100\nb 350 700\nc 200 800\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e900\u003c/pre\u003e"}}]}