E. Defense of Valor League
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Once there was a highly anticipated e-sports championship, the 2020 League of Legends World Championship, where DWG defeated SN 3 to 1 in the finals.

Even though Oscar is a player of the game Defense of Valor League (DoVL) — a recently developed MOBA game, he could also felt the excitement of the finals, especially when the player SN Bin took the extraordinary PENTA KILL using the champion Fiora.

While watching the final games, he noticed that two teams always picked the red side when they were able to choose to act as the blue team or the red team. One possible explanation for such phenomenon may be that the red team holds the last pick, or Counter Pick, that may help team choose one good hero countering the opponent's lineup. He fell into deep thought: in the ban pick phase of the game, how much advantage or disadvantage does the blue team have?

To investigate the problem he decided to do some experiments in DoVL, which is a $$$p$$$-player versus $$$p$$$-player game. To start a game, each of the two teams need to pick $$$p$$$ distinct heroes of all $$$n$$$ heroes to form a lineup by ban pick phase, as described as follows.

  • Ban Phase  Two teams take $$$b$$$ turns to ban a hero (to clarify, each team has $$$b$$$ turns), starting from the blue team. All heroes banned should be distinct. However, teams are allowed to decide not to ban any hero in any of their turns (known as an empty ban). The banned heroes can not be chosen in the pick phase by both teams.
  • Pick Phase  Two teams take turns to pick heroes to form a lineup. The blue team first picks $$$1$$$ hero. Then starting from the red team, the two teams take turns to pick $$$2$$$ heroes, until only one hero is missing in one team's lineup, and that team finally picks their last hero. All heroes picked should be distinct and not banned.

To evaluate the lineup quality of picking, we follow three perspectives to calculate a score.

  • Strength  Some heroes are naturally stronger than others in the current game. If one team picked hero $$$i$$$, they will earn $$$c_{ii}$$$ points.
  • Combo  Some heroes will be stronger when working with one another. If two different heroes $$$i$$$ and $$$j$$$ are in the same team, the team will earn $$$c_{ij}$$$ points for such a combination. It's guaranteed that $$$c_{ij} = c_{ji}$$$, but you should not double count both $$$c_{ij}$$$ and $$$c_{ji}$$$.
  • Counter  Some heroes make some specific opponents hard to perform well. If heroes $$$i$$$ and $$$j$$$ are in different teams, the team picking $$$i$$$ will earn $$$d_{ij} / 2$$$ points, while the team picking $$$j$$$ will earn $$$d_{ji} / 2$$$. It's guaranteed that $$$d_{ij} = -d_{ji}$$$.

Formally, suppose the lineup of the blue team is $$$(x_1, \ldots, x_p)$$$ and the one of the red team is $$$(y_1, \ldots, y_p)$$$. The total advantage (or disadvantage if negative) of the blue team can be evaluated by

$$$$$$ (\sum_{i=1}^p c_{x_i x_i} + \sum_{i=1}^p\sum_{j=i+1}^p c_{x_i x_j} + \sum_{i=1}^p \sum_{j=1}^p \frac 12 d_{x_i y_j}) - (\sum_{i=1}^p c_{y_i y_i} + \sum_{i=1}^p\sum_{j=i+1}^p c_{y_i y_j} + \sum_{i=1}^p \sum_{j=1}^p \frac 12 d_{y_i x_j}). $$$$$$

Given all the information above, can you help Oscar to calculate the advantage (or maybe disadvantage) the blue team will take when the two teams act optimally? It's not an easy task, so you may claim that you outperform the coaches of the world champions if you manage to solve this problem!

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 10$$$). Description of the test cases follows.

For each test case, the first line contains three integers $$$b$$$, $$$p$$$ and $$$n$$$ ($$$p \geq 1$$$, $$$b \geq 0$$$, $$$b + p \leq 5$$$, $$$2(b + p) \leq n \leq 12$$$).

The $$$i$$$-th of the next $$$n$$$ lines contains $$$n$$$ integers $$$c_{i1}, \ldots, c_{in}$$$ ($$$0 \leq c_{ij} \leq 1000$$$). It is guaranteed that $$$c_{ij} = c_{ji}$$$.

The $$$i$$$-th of the next $$$n$$$ lines contains $$$n$$$ integers $$$d_{i1}, \ldots, d_{in}$$$ ($$$-1000 \leq d_{ij} \leq 1000$$$). It is guaranteed that $$$d_{ij} = -d_{ji}$$$.

It is also guaranteed that, for test cases, where $$$T \geq 5$$$ the value of $$$c_{ij}$$$ ($$$i \leq j$$$) and $$$d_{ij}$$$ ($$$i \lt j$$$) are generated independently uniformly randomly.

Output

For each test case, print on a line an integer representing the advantage (or disadvantage if negative) of the blue team.

Example
Input
4
0 2 4
5 0 0 0
0 2 9 0
0 9 2 0
0 0 0 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 1 4
4 0 0 0
0 3 0 0
0 0 2 0
0 0 0 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 1 3
0 0 0
0 0 0
0 0 0
0 -1 1
1 0 -1
-1 1 0
1 1 4
9 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 -1 1
0 1 0 -1
0 -1 1 0
Output
-4
1
-1
1
Note

Explanation for the four examples:

  1. Even hero $$$1$$$ is a strong choice, but there's an unstoppable combo of $$$2$$$ and $$$3$$$. So the blue team must pick one of these two heroes to minimize disadvantage. In the red team's turn hero $$$1$$$ and the remaining one of $$$\{2, 3\}$$$ will be picked. The disadvantage of the first team is $$$(2 + 1) - (5 + 2) = -4$$$.

  2. It can be proven that no matter which hero the blue team bans, the red team can always make the strongest two unbanned heroes differ by $$$1$$$ in strength.

  3. Do you remember the game Rock, Paper, Scissors? The one who can see the other's choice can always win.

  4. The blue team will ban any of $$$\{2, 3, 4\}$$$. Otherwise, the red team will act so that only hero $$$1$$$ is banned (maybe using an empty ban), leading to a Rock, Paper, Scissors game which puts the blue team at a disadvantage.