#1972. [USACO07OPEN] Cheapest Palindrome G

[USACO07OPEN] Cheapest Palindrome G

题目描述

给定一个由 nn 个不同的小写字母构成的长 mm 的字符串 ss。可以通过在 s\bm{s} 的任意位置增减字母将 ss 改为回文串。增减字母的花费不同,求最小花费。

输入格式

第 11 行是两个整数 n,mn,m。

第 22 行是字符串 ss。

接下 nn 行,每行一个字符 cc 和两个整数 x,yx,y,表示添加一个 cc 的花费为 xx,删除一个 cc 的花费为 yy。

输出格式

只有 11 行,表示最小花费。

样例

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

题目来源:洛谷 P2890