Description

给定一个由 $n$ 个不同的小写字母构成的长 $m$ 的字符串 $s$。可以通过在 $\bm{s}$ 的任意位置增减字母将 $s$ 改为回文串。增减字母的花费不同，求最小花费。

Input Format

第 $1$ 行是两个整数 $n,m$。

第 $2$ 行是字符串 $s$。

接下 $n$ 行，每行一个字符 $c$ 和两个整数 $x,y$，表示添加一个 $c$ 的花费为 $x$，删除一个 $c$ 的花费为 $y$。

Output Format

只有 $1$ 行，表示最小花费。

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

900

Hint

对于 $100\%$ 的数据，$1\le m\le2\times10^3,1\le n\le 26,0\le x,y\le 10^4$。

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