306024 - 增减字符改造回文串

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

第一行是两个整数 n 和 m （1 ≤ m ≤ 2 × 103，1 ≤ n ≤ 26）。 第二行是一个字符串 s。 随后 n 行，每行一个字符 c 和两个整数 x, y （0 ≤ x, y ≤ 104），表示添加一个 c 的花费为 x，删除一个 c 的花费为 y。

输出一个数，表示最小花费。