测试数据来自 system/2508

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　我们可以在字符串中的任意位置上添加或删除字符，把一个字符串变换成另一个字符串。插入或删除字符都有一定的成本，这取决于要添加或删除的字符。

　　那么要把字符串 \(S\) 和 \(T\) 变成一样，最少需要多少成本？

【输入格式】

　　第一行是两个空格分隔的整数：\(K\)，其中 \(K\) 表示字符串中仅会出现K个不同的字符。接下来的两行分别是字符串 \(S\) 和 \(T\)。再接下来的 \(K\) 行，每行包含三个用空格分开的数据，第一个是一个英文字母 \(C\)，第二个是一个整数 \(W_1\)，第三个是一个整数 \(W_2\)，分别表示在字符串中插入和删除一个英文字母 \(C\) 的成本。

【输出格式】

　　一个整数，表示把 \(S\) 变换成 \(T\) 的最小成本。

【输入输出样例】

　Input

3
abcb
cba
a 100 110
b 35 70
c 20 80 

　Output

145

【输入输出样例解释】

　　如果我们在末尾插入一个“a”来获取“abcba”，那么费用将是1000；
　　如果我们从头开始删除“a”来获取“bcb”，那么费用将是1100；
　　如果我们在前面插入“bcb”得到“bcbabcb”，成本将是350+200+350=900，这是最小的。

【数据说明】

　　对于 \(100\%\) 的数据 \(1≤N≤26\)，\(1≤M≤2000\)，\(0≤\)成本\(≤10000\)。

【来源】

　　Mr.he