最近，Raven 沉迷于一款名为“连连看”（Xian Xiang）的游戏。

游戏开始时，在一个 $n \times m$ 的矩形区域内放置了一些物体。每个物体都有 $k$ 种属性。玩家可以通过一条折线连接并消除任意两个物体，折线的每一部分要么是水平的，要么是垂直的。然而，折线最多只能改变一次方向，且其路径上不能有任何其他物体（规则类似于连连看）。每当一对物体被消除，它们所在的单元格就会变为空白，并根据这两个被消除物体匹配的属性数量获得相应的分数。如果两个物体之间有 0 个共同属性，得分为 $s_0$；如果有 1 个共同属性，得分为 $s_1$，以此类推；如果有 $p$ 个共同属性，得分为 $s_p$。

游戏设有排行榜，Raven 渴望登上榜首。因此，他必须尽力在游戏中获得最高分。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 20$)，表示测试用例的数量。

每个测试用例以三个正整数 $n, m, k$ ($1 \le n, m \le 7, 1 \le k \le 5$) 开头，分别表示矩形的长、宽以及物体的属性数量。

接下来有 $n \times m$ 个长度为 $k$ 的字符串，表示对应的物体。初始时，如果单元格为空，则字符串为 $k$ 个“-”；如果单元格内有物体，则字符串为 $k$ 个小写字母。每个小写字母代表一种属性。如果两个被连接物体的字符串在相同位置上的字母相同，则表示这两个物体在该位置具有相同的属性。

最后一行包含 $k + 1$ 个正整数 $s_0, s_1, \dots, s_k$ ($1 \le s_i \le 10000$)。

保证每组数据中的物体总数为偶数，且不超过 18 个。

输出格式

对于每个测试用例，输出一行一个整数，表示游戏可能获得的最高得分。

样例

样例输入 1

3
2 2 3
aaa aaa
bbb bbb
1 10 100 1000
2 3 3
aaa --- bbb
bbb --- aaa
1 10 100 1000
1 4 3
aaa bba abb aaa
1 10 100 1000

样例输出 1

2000
2
1010

说明

在第一个样例中，消除第一行和第二行的两个物体，可以得到 2000 分。 在第二个样例中，由于相同的物体无法连接，只能得到 2 分。 在第三个样例中，先消除中间的两个物体，然后再消除最左侧和最右侧的两个物体。