Problem Description

“Life is like a box of chocolates, you never know what the next one tastes like.”

Mingming received a large bar of chocolate. It contains many small pieces arranged in $n$ rows and $m$ columns. Each small piece has its own unique pattern: some are starfish, some are shells, some are conchs... and some have been crushed so that their patterns can no longer be recognized. Mingming assigns each piece a deliciousness value $a_{i,j}$ ($0\le a_{i,j}\le 10^6$). The larger this value is, the more delicious the piece is.

Just as Mingming swallowed and was about to enjoy it, Zhouzhou appeared magically. Seeing Zhouzhou’s pleading eyes, Mingming decided to pick some pieces to share with Zhouzhou.

Zhouzhou hopes that the selected chocolate pieces are connected (two pieces are connected if and only if they share a common edge), and that these pieces contain at least $k$ ($1\le k\le 5$) different types. The crushed pieces cannot be selected.

Mingming wants to satisfy Zhouzhou, but he is also a bit “stingy” and wants to keep as much deliciousness as possible for himself. Therefore, he wants the number of selected pieces to be as small as possible. If, under the condition that the number of selected pieces is minimal, the median of the deliciousness values can be as small as possible, that would be even better. (We define the median of $n$ numbers as the $\left\lfloor\frac{n+1}{2}\right\rfloor$-th smallest number.)

Can you help Mingming?

Input Format

Each test point contains multiple groups of testdata.

The first line contains a positive integer $T$ ($1\le T\le 5$), indicating the number of testdata groups.

For each group of testdata:

The first line contains three positive integers $n$, $m$, and $k$.

The next $n$ lines each contain $m$ integers, describing the pattern type $c_{i,j}$ of each piece. If $c_{i,j}=-1$, this piece has been crushed and cannot be selected.

The next $n$ lines each contain $m$ integers, describing the deliciousness value $a_{i,j}$ of each piece.

Output Format

Output a total of $T$ lines. Each line contains two integers separated by a space: the minimum number of pieces and the minimum possible median deliciousness value.

If for some testdata group there is no valid selection方案, output two $-1$ on the corresponding line.

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 3

9 5

Hint

$\text{A}$: If the minimum number of pieces is correct, but the minimum median is wrong, the contestant can get $80\%$ of the score for this test point.
$\text{B}$: If the minimum number of pieces is correct, but the minimum median is wrong, the contestant can get $60\%$ of the score for this test point.

Translated by ChatGPT 5