No submission language available for this problem.

Background

Special for beginners, ^_^

Description

约翰在每头牛身上都安装了一个 id 标签（电子身份标签），当牛通过扫描仪时，系统会读取这个标签。每个 id 标签都是从 n (1 ≤ n ≤ 26) 个小写字母的字母表种提取的长度为 m （1 ≤ m ≤ 2000) 的字符串。牛有时试图通过倒退来欺骗系统。当一头牛的 id 标签是 "abcba" 时，不管它朝哪个方向走，都会读到相同的 id 标签，而一头牛的 id 标签是 "abcb" 时，可能会被读到两个不同的 id 标签（abcd 和 bcba）。约翰想修改牛的 id 标签，这样无论牛从哪个方向走过，都可以读到相同的内容。例如，"abcb" 可以通过在末尾添加 'a' ，形成 "abcba" 这样的 id 标签就是回文。将 id 标签更改为回文的其它方法包括将 "bcb" 添加到开头，产生 id 标签 "bcbabcb"；或删除字符 'a'，产生 id 标签 "bcb"。

可以在字符串中的任意位置添加或删除字符，从而生成比原始字符串长或短的字符串。

给定牛的 id 标签及添加、删除每个字符的成本(0 ≤ 成本 ≤ 10000)，求解使 id 标签满足回文字符串的最小成本。一个空的 id 标签被认为已满足要求。只有包含相关成本的字母才可以被添加到字符串中。

Format

Input

第 1 行包含两个整数 n 和 m

第 2 行包含 m 个字符，表示初始的 id 标签。

第 3 ... n+2 行的每一行都包含一个字符和两个整数，分别表示添加和删除该字符的成本。

Output

单行输出更改给定标为回文的最小成本

Samples

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

900

Explain

若在 abcb 末尾添加一个 a，则得到 abcba，成本 1000

若将 abcb 开头的 a 删除，则得到 bcb，成本 1100

若在 abcb 开头插入 bcb，则得到 bcbabcb，成本是 350 + 200 + 350 = 900，这个成本最小。

Limitation

1s, 1024KiB for each test case.