19075번 - K-matching 다국어

문제

Consider a graph $G$ with $n \cdot m$ nodes $(i, j)$ (1ドル \leq i \leq n,ドル 1ドル \leq j \leq m$). There is an edge between two nodes $(a, b)$ and $(c, d)$ if and only if $|a - c| + |b - d| = 1$. Each edge has a weight.

Calculate the minimum weight of a $K$-matching in $G$.

An edge set $S$ is a matching of $G = \langle V, E \rangle$ if and only if each node in $V$ is connected to at most one edge in $S$. A matching $S$ is a $K$-matching if and only if $|S| = K$. The weight of a matching $S$ is the sum of the weights of the edges in $S$. And finally, the minimum weight $K$-matching of $G$ is defined as the $K$-matching of $G$ with the minimum possible weight.

입력

The first line contains an integer $t,ドル the number of test cases (1ドル \leq t \leq 1000$). It is guaranteed that there are at most 3ドル$ test cases with $n > 100$.

For each test case, the first line contains three integers $n,ドル $m$ and $K$ (1ドル \leq n \leq 4 \cdot 10^4,ドル 1ドル \leq m \leq 4,ドル 1ドル \leq K \leq \lfloor \frac{n \cdot m}{2} \rfloor$).

Then $n - 1$ lines follow, each of these lines contains $m$ integers $A_{i, j}$: the weights of edges between $(i, j)$ and $(i + 1, j)$ (1ドル \leq A_{i, j} \leq 10^9$).

If $m > 1,ドル then $n$ more lines follow, each of these lines contains $m - 1$ integers $B_{i, j}$: the weights of the edge between $(i, j)$ and $(i, j + 1)$ (1ドル \leq B_{i, j} \leq 10^9$).

출력

For each test case, print a single line with a single integer: the required minimum weight.

제한

힌트