Description
Domo is a brilliant dog. Now he needs to solve these problems to pass the I2P.
In the mid2 practice, Domo has solved the N-Queens M-Rooks Problem, but now, there are some variant problems that need your help to finish.
Note: This problem is separated into three parts, each with different constraints. The differences between each part will be highlighted in red.
The first part of the chess puzzle is N-Queens M-Rooks Problem with threshold.
You need to find how many ways to place N queens and M rooks on an (N+M) × (N+M) chessboard such that no two of queens or rooks can attack each other in 1 step.
In addition, there's an integer in each block on the chessboard. The sum of the blocks where you place a chess piece cannot exceed K.
For N = 1, M = 2, K = 5, and the chessboard is shown below:
1 1 6 1 1 1 1 1 1
There're 3 solutions:
( 0 means empty spot, Q means queen, R means rook. )
Q 0 0 0 R 0
0 0 R R 0 0
0 R 0 0 0 Q
0 R 0
0 0 R
Q 0 0
Notice that this is not a solution, since the sum of blocks is 8 (but K is 5).
0 0 Q | 1 1 6 R 0 0 | 1 1 1 0 R 0 | 1 1 1
Possible move of Queen:
Possible move of Rook:
Input
The first line consists of an integer T (1 ≤ T ≤ 10) indicating the number of test cases.
Starting from the second line, the input will be test cases.
For each test case, the first line consists of three integers N, M, and K (1 ≤ N, M ≤ 9, 1 ≤ N+M ≤ 9, 1 ≤ K ≤ 1000)
For the next N+M line, each line consists of N+M numbers A1, A2, ..., AN+M, indicating integers in the chessboard. (1 ≤ Ai ≤ 1000)
Output
For each test case, output the number of ways that you can place chesses.