33OJ
登录 注册

#P17643. [ICPC 2019 Yinchuan R] Xian Xiang

[ICPC 2019 Yinchuan R] Xian Xiang

Problem Description

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×mn \times m rectangle. Every object has kk 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 00 common attribute between two objects, the score will be s0s_0; if there is 11 common attribute, the score will be s1s_1, ...; and if there are pp common attributes, the score will be sps_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.

Input Format

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

Each case starts with three positive integers n,m,k (1≤n,m≤7,1≤k≤5)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×mn \times m strings with a length of kk, showing the corresponding objects. Initially, if the cell is blank, the string is assigned with kk "-"; if there is an object in the cell, the string is assigned with kk 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+1k+1 positive integers s0,s1,⋯ ,sk (1≤si≤10000)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 1818.

Output Format

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

Hint

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

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

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