#P3280. Cheapest Palindrome

Cheapest Palindrome

本题没有可用的提交语言。

P2890 [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 行,表示最小花费。

输入输出样例 #1

输入 #1

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

输出 #1

900

说明/提示

对于 100%100\% 的数据,1m2×103,1n26,0x,y1041\le m\le2\times10^3,1\le n\le 26,0\le x,y\le 10^4

by @\mathrm{by\ @}Fish_Know_Forever\mathrm{Fish\_Know\_Forever}