测试数据来自 system/2508

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

---

【问题描述】

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

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

【输入格式】

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

【输出格式】

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

【输入输出样例】

　Input

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

　Output

145

【输入输出样例解释】

　　一种最优操作方案如下：
　　在"abcb"前插入一个'c'，得到"cabcb"，在把两个'b'删除，得到"cac”；
　　删除"cba"中的'b'，得到"ca"，在末尾插入一个'c'，得到"cac”；
　　总代价为：2 * 20 + 3 * 35 = 145。

【数据说明】

　　对于 \(100\%\) 的数据 \(1≤K≤26\)，\(1≤字符串长度≤2000\)，\(0≤\)成本\(≤10000\)。

【来源】

　　Mr.he