Problem1096--魔术师PIPI

1096: 魔术师PIPI

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 97  Solved: 46
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI是一个魔术师,但它只会一种魔术——把字符串变成回文串。
现在有一个由N种不同小写字母构成的长度为M的字符串S,PIPI可以通过删除或增加S中已有字符使S变成回文串,但是增加或删除不同的字符需要消耗不同的MP。
给出串中每种字母增加或删除消耗的MP,请你帮PIPI计算需要消耗的最少的MP是多少。
PS:增加和删除可以作用于串的任何位置。

Input

多组数据
第一行给出两个整数N,M,1<=N<=26,1<=M<=2000
第二行为一个字符串
接下来N行,每行一个字符c,两个整数add,del,分别表示增加和删除字符c所需要的MP。不超过10000.

Output

输出一个整数,表示最少所需MP。

Sample Input

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

Sample Output

900

Source/Category