该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

最小的回文代价

题目描述

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

输入格式

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

900

说明/提示

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