极限逃生

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

 大宝来到一个古埃及墓地中探险,不过他遇到了危险,被困在了一个房间里。房间中有一个大石台,上边有m个石块,每个石块上有一个字符(小写字母),假设石台足够长。同样的,房间的地上有密密麻麻的石块,每个石块上都对应一个字符,你可以认为石块有无穷多个,不同字符的石块重量不一样。
大宝发现房间的墙壁上有一段文字,讲述的是怎么走出这个房间,不过年代久远,有的字迹已经看不清楚了。经过大宝苦心研究,终于发现了走出房间的办法。其实很简单,就是把石台上的字符串通过添加和搬走石块构成一个回文串(正序和倒序读都相等,如"abcba")。不过大宝之前消耗了太多的体力,如果他一个劲的蛮干的话可能在还没有离开房间之前就已经筋疲力尽挂掉了。经过他的计算,从石台上搬走某字符str[i]消耗d单位的体力,从房间里找到str[i]放到石台上消耗a单位的体力,请你帮大宝计算一下最少需要消耗多少单位的能量能够让他走出房间。
 

Input

 第一行:输入n,m。n(1 <= n <= 26)表示房间里有多少种字符,m(1<= m <= 2000)表示石台上原有m个石块。
第二行:输入石台上石块对应的字符串;
第三到n+2行:格式为str a, d.表示字符str添加到石台上消耗a单位体力,从石台上搬走消耗b单位体力;

Output

 输出大宝走出房间最小需要消耗的能量

Sample Input

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

Sample Output

900

Hint

 abcb可以改变成bcbabcb,这样得到最小值共消耗350+200+350 = 900的能量。

Source

von