1182: 回文串

Memory Limit：128 MB Time Limit：1.000 S Judge Style：Text Compare Creator：
Submit：25 Solved：8

Description

"回文串"是一个正着读和反着读都一样的字符串，例如"level"和"noon"都是回文串，而"ac"不是回文串。

现在你有一个长度为n且仅由小写字母构成的字符串s，同时你还会m种普通魔法和一种超级魔法，第t种普通魔法可以把一个字母ai转换为bi，但需要消耗ci点法力。超级魔法可以把一个任意的字母转换为另一个任意的字母，但需要消耗w点法力。

每一种普通魔法都是单向的，也就是说只能把ai转换为bi，而不能把bi转换为aia_i。

并且施放一次魔法（包括普通魔法和超级魔法）只能变换一个位置上的字母。例如你有一种普通魔法可以把字母'x'变为字母'y'，那么对于字符串"xxx"，不管是只使用普通魔法还是只使用超级魔法，或者是普通魔法和超级魔法混合使用，你都必须要施放三次魔法才能将它变为字符串"yyy"。

现在你需要把字符串 ss 变成一个回文串，请计算最少需要消耗多少点法力。

不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

第一行输入一个正整数T (1<=T<=1000),表示有T组测试数据。
对于每一组测试数据：
第一行输入三个正整数n,m,w (1<=n,m<=2*10^5,1<=w<=10^9),  分别表示字符串s的长度为n，普通魔法的种类数为m，超级魔法消耗的法力为w。
第二行输入一个长度为n且仅由小写字母构成的字符串s。

接下来m行，每行输入两个小写字母ai、bi和一个正整数ci(1<=ci<=10^9) 表示第ti种普通魔法可以把一个字母ai转换为bi，且需要消耗ci点法力。

Output

对于每组测试数据输出一行一个整数，表示最少需要花费的法力。

Sample Input Copy 

2
5 3 3
abcde
a z 1
a e 1
b d 5
4 1 3
noon
a a 1

Sample Output Copy 

4
0

HINT

第一组测试数据： 使用一次第二种普通魔法，把'a'变成'e'，再使用一次超级魔法把'b'变成'd'，最后得到"edcde"。

第二组测试数据："noon"已经是回文串了所以不需要使用任何魔法。

从ai变成bi的过程中可能需要经过多个中间字符

Source/Category