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.
Sample Input
3 4
abcb
a 1000 1100
b 350 700
c 200 800