"Life is like a box of chocolates, you never know what you're going to get."
Mingming received a large bar of chocolate consisting of $n$ rows and $m$ columns of small pieces. Each piece has a unique pattern $c_{i,j}$, such as starfish, seashells, conch shells, etc. Some pieces are crushed and their patterns are no longer identifiable. Mingming assigned a deliciousness value $a_{i,j}$ ($0 \leq a_{i,j} \leq 10^6$) to each piece; the higher the value, the more delicious the piece.
Just as Mingming was about to enjoy the treat, Zhouzhou appeared. Seeing Zhouzhou's pleading eyes, Mingming decided to select some pieces to share.
Zhouzhou wants the selected chocolate pieces to be connected (two pieces are connected if and only if they share an edge) and to contain at least $k$ ($1 \leq k \leq 5$) distinct patterns. Crushed pieces cannot be selected.
Mingming wants to satisfy Zhouzhou's wish but is a bit "stingy," wanting to keep as much deliciousness for himself as possible. Therefore, Mingming wants to minimize the number of selected chocolate pieces. If there are multiple ways to achieve the minimum number of pieces, he wants to minimize the median of the deliciousness values (the median of $n$ numbers is defined as the $\lfloor \frac{n+1}{2} \rfloor$-th smallest number).
Can you help Mingming?
Input
The input is read from standard input.
Each test case contains multiple test data sets.
The first line contains a positive integer $T$ ($1 \leq T \leq 5$), representing the number of test cases.
For each test case:
The first line contains three positive integers $n, m$, and $k$.
The next $n$ lines, each containing $m$ integers, represent the patterns $c_{i,j}$ of each piece. If $c_{i,j} = -1$, it means the piece is crushed and cannot be selected.
The next $n$ lines, each containing $m$ integers, represent the deliciousness values $a_{i,j}$ of each piece.
Output
Output to standard output.
The output consists of $T$ lines, each containing two integers separated by a space: the minimum number of pieces and the minimum median deliciousness value.
If no valid selection scheme exists for a test case, output two $-1$s on the corresponding line.
Examples
Input 1
1
5 4 5
3 4 3 4
5 5 -1 5
-1 4 5 5
5 5 4 2
1 -1 2 4
1 3 1 1
3 2 3 3
4 4 4 5
8 9 9 5
7 2 6 3Output 1
9 5Subtasks
| Test Case ID | $n, m$ Constraints | $c_{i,j}$ Constraints | Scoring Notes |
|---|---|---|---|
| 1 | $n = 1, 1\leq m \leq 233$ | $c_{i,j} = -1$ or $1\leq c_{i,j} \leq n \times m$ | If the minimum number of pieces is correct but the minimum median is incorrect, the contestant receives $80\%$ of the points for this test case. |
| 2 | $1\leq n\times m \le 20$ | ||
| 3 | $n = 2, m = 15$ | ||
| 4 | |||
| 5 | $1\leq n\times m \leq 30$ | ||
| 6 | |||
| 7 | $1 \leq n\times m \leq 50$ | $c_{i,j} = -1$ or $1\leq c_{i,j} \leq 8$ | |
| 8 | |||
| 9 | |||
| 10 | $ 1 \leq n\times m \leq 233$ | ||
| 11 | If the minimum number of pieces is correct but the minimum median is incorrect, the contestant receives $60\%$ of the points for this test case. | ||
| 12 | |||
| 13 | $c_{i,j} = -1$ or $1\leq c_{i,j} \leq 14$ | ||
| 14 | |||
| 15 | |||
| 16 | $c_{i,j} = -1$ or $1\leq c_{i,j} \leq n \times m$ | ||
| 17 | |||
| 18 | |||
| 19 | |||
| 20 |