问题描述

简单喜欢收集奇奇怪怪的石子，他将这些石子按照外观分成了26种不同的类别，每一种类别恰好都能用不同的小写字母表示。按照收集的时间，简单将这些石子摆成了 $n*n$ 大小的正方形，可他有强迫症，想要这个矩阵上下左右完美对称，但是他又不想调整石子的顺序。好在他会 $k$ 种普通雕刻手艺，花费一定时间后能够将某种类型的石子转换成另一种类型的石子。同时，他还会一种万能的雕刻方法，能将任意类型的石子转换成其他任意类型的石子，但是每一次转换需要花费 $m$ 个单位时间。他想知道最少需要多少时间能使得这个矩阵上下左右完美对称，于是他向你求助。

输入格式

第一行输入一个正整数 T, 表示有 T 组测试数据。

对于每一组测试数据：

第一行输入三个正整数 n, m, w，表示正方形的边长为n，简单所掌握的普通雕刻手艺的种类数为 m，万能的雕刻方法消耗的时间为 w。

接下来 m 行，每行输入两个小写字母 $a_i, b_i$ 和一个正整数 $c_i$ ，表示第 i 种普通雕刻手艺可以把一个字母 $a_i$ 转换为 $b_i$ ，且需要消耗 $c_i$ 单位时间。

最后给出 $n*n$ 行的矩阵，每个字母分别表示该位置上的石子的种类。

输出格式

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

输入样例

1
3 2 50
a z 1
z c 1
a b c
b c a
c a b

输出样例

152

说明

假设下标从0开始，那么所谓的完美对称就是说，对于一个n*n大小的矩阵上任意一点（i，j），其石子种类必定与（n-1-i，j）和（i，n-1-j）处的石子种类一致，这就是所谓的上下对称和左右对称。

保证所有出现的字母都是小写字母！

对于第一个样例来说，其中一种方案是最终将其转换成

c b c
b c b
c b c

其代价为152。

评测数据规模

对于所有评测数据，

$1 \le T \le 1000, 1 \le n, m \le 100, 1 \le w, c_i \le 1000$