给定一个长度为 $m(m \leq 2000)$ 的小写字母字符串, 在给定组成该字符串的 $n(n \leq 26)$ 个字符的添加和删除费用, 求使原字符串变为回文串的最小费用。

输入

• 第一行包含两个整数 $n$ 和 $m$
• 第二行为长度为 $m$ 的字符串, 接下来有 $n$ 行, 每行首先是一个小写字母接下来有两个整数分别表示添加和删除该字母的费用(空格隔开)

输出

• 一个整数，表示把字符串变为回文串的最小费用