Problem Description
Each member of WHU ACM Team developed his/her own Five in a row AI application. They are planning to hold an AI competition on the online arena they just developed.
Each AI competitor has to compete with every other participator once. The winner of each game is awarded with credits while the loser gets nothing. No one gets credits in a tied game.
Every competitor has an experience point, which is crucial to the game. In each game, the competitor with higher experience point wins, except for tied games, in which two competitors have the same experience point.
Those AIs are so clever that they will learn from every game. That is to say, no matter win or lose, AIs' experience point may increase after each game.
Alex, the team leader, has the privilege to arrange the game order. He wants to maximum his credit. Please help him solve the problem.
Input
The input consists of several test cases. The first line of the input consists of an integer T, indicating the number of test cases.
Each test case starts with a line consist of an integer N, indicating the number of competitors. Each of the following N lines consists of N integers Eij, indicating the experience point the i-th competitor will increase after the game with the j-th competitor. Then, each of the following N lines consists of N integers Wij, indicating the credit the i-th competitor will gain if wins the game with the j-th competitor.
The last line of each test case consists of N integers Si, indicating the initial experience point of each competitor.
By the way, Alex is the first player.
Technical Specification
- 1 ≤ T ≤ 11
- 1 ≤ N ≤ 13
- 0 ≤ Wij ≤ 10
- 0 ≤ Eij, Si ≤ 1000
Output
For each test case, output a single line consists of the maximum credit Alex may get.
Sample Input
2
2
0 1
1 0
0 1
1 0
1 1
3
0 5 2
0 0 0
0 0 0
0 10 1
1 0 1
1 0 0
1 10 5
Sample Output
0
1
