410440: GYM104021 L Xian Xiang

In recent days, Raven is addicted to a game called Xian Xiang.

At the beginning of this game, there are some objects in an $$$n \times m$$$ rectangle. Every object has $$$k$$$ types of attributes. The player could delete any two objects by linking these two objects with a folding line, each part of which is either horizontal or vertical. However, the line can only change direction at most once, and there cannot be any object on its path (the rule is similar to that of Lian Lian Kan). Whenever the objects are deleted, the cells of the object will be left empty, and a score will be given according to the number of matching attributes of the two deleted objects. If there is $$$0$$$ common attribute between two objects, the score will be $$$s_0$$$; if there is $$$1$$$ common attribute, the score will be $$$s_1$$$, ...; and if there are $$$p$$$ common attributes, the score will be $$$s_p$$$.

There is a scoreboard and Raven is eager to go to the top of the scoreboard. So he must try his best to get the highest score in the game.

The first line is an integer $$$T~(1 \le T \le 20)$$$, which indicates the number of test cases.

Each case starts with three positive integers $$$n, m, k~(1 \le n, m \le 7, 1 \le k \le 5)$$$, representing the length, width, and the number of the attributes of the object respectively.

Next, there are $$$n \times m$$$ strings with a length of $$$k$$$, showing the corresponding objects. Initially, if the cell is blank, the string is assigned with $$$k$$$ "-"; if there is an object in the cell, the string is assigned with $$$k$$$ small-case letters. Each small-case letter represents a kind of attribute. If the letters at the same position of the string are the same for the linked two objects, it indicates that the two objects have the same attribute of that position.

Then there are $$$k+1$$$ positive integers $$$s_0, s_1, \cdots, s_k~(1 \le s_i \le 10000)$$$ in the last line for every group of data.

It is guaranteed that the number of objects in each group of data is an even number and no more than $$$18$$$.

For each case, output an integer in a line, showing the highest possible score for the game.

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

2000
2
1010

In the first sample, delete two objects in the first row and the second row and you will score $$$2000$$$ points.

In the second sample, as the same objects cannot be linked, you can only score $$$2$$$ points.

In the third sample, delete two objects in the middle, and then delete two objects at the far left and far right.