1762: 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*m rectangle. Every object has k types of attributes. The player could delete any two objects by linking these two objects with a line. However, the line can only turn once at most, and there cannot be any object in its path (the rule is similar to that of Lian Lian Kan). Every time when the objects are deleted, the cells of the object will be left empty, and a score will be given according to the matching attributes of the two deleted objects. If there is 0 same attribute between two objects, the score will be S [0]; if there is 1 common attribute, the score will be S [1], …; if there is p common attributes, the score will be S [p]. There is a scoreboard. Raven is eager to go to the top of the scoreboard, so he must try his best to get high score in the game.

The first line of the input contains an integer T, which indicates the number of test cases. Each case starts with three positive integers, n, m, k (1 <= n, m <= 7, 1 <= k <= 5), representing the length, width, and the number of the attributes of object respectively. Next there are n*m strings of k long, showing the corresponding objects. If the cell is blank in the very beginning, the string is assigned with k “-”; if there is an object in the cell in the beginning, 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. Input should make sure that the total number of objects in each group of data is an even number and that the total objects should not be more than 18. There are k+1 positive integers in the last row for every group of data, representing respectively the score for 0 common attribute, the score for 1 common attribute,…., the score for k common attributes. Input shall make sure: the more common attributes, the more score points.

For each case, output a number, 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

Sample 1: Delete two objects in the first row and the second row, and you may score 2000 points. Sample 2: As the same objects cannot be linked (at least two turnings shall be made), so you many only score 2 points. Sample 3: Delete two objects in the middle, and then delete two objects at the far left and far right.