题目描述

跟踪所有的奶牛是一项棘手的任务，因此 FJ 安装了一个系统来实现自动跟踪。
他在每头奶牛身上安装了一个电子标签，当奶牛经过扫描仪时，系统将扫描该标签。每个标签的内容都是长度为 $m (1 \le m \le 2000)$ 的字符串（全部使用小写罗马字母）。

奶牛是一种淘气的动物，有时会试图通过向后行走来欺骗系统。
例如：标签为 abcba 的奶牛无论朝哪个方向行走都会读取相同的信息，但标签为 abcb 的奶牛可能会拥有两个不同的身份： abcb 和 bcba。

FJ 希望更改奶牛的标签，使奶牛们无论怎么走，它们被读取的身份都一样。
例如：abcb 可以通过在末尾添加 a 来更改，以形成回文串： abcba。将标签更改为回文的其他方法包括在开头添加 bcb 形成 bcbabcb，抑或删除字母 a 以生成标签 bcb。总之，约翰可以在任意位置删除或插入一些字符使字符串变成回文串。

不幸的是，由于标签是电子的，每个字符的插入或删除都有成本 $s\ (0 \le s \le 10000)$。给定一头奶牛的身份标签和增加或删除相关字母的费用，找出把原来字符串变成回文的最小费用。
注意：空字符串也是回文。

输入格式

第一行：两个由空格分隔的整数：$n$ 和 $m$。

第二行：这一行正好包含构成初始标签的 $m$ 个字符。

第三行到 $n+2$ 行：每行包含三个空格分隔的整数：一个字符和两个整数，分别是添加该字符和删除该字符的成本。

输出格式

一行，一个表示更改此标签的最小成本的整数。

样例解释

如果在末尾插入 a，得到 abcba，成本为 $1000$。如果删除开头的 a，得到 bcb，成本为 $1100$。如果我们在字符串开头插入 bcb，成本为 $350+200+350=900$，这是最小成本。