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.

Find 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$. The minimum weight $K$-matching of $G$ is the $K$-matching with the smallest possible weight.

The first line contains an integer $t$, the number of test cases ($1 \leq t \leq 1000$). At most $3$ test cases have $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 containing $m$ integers $A_{i, j}$: the weights of the 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 containing $m - 1$ integers $B_{i, j}$: the weight 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 containing the minimum weight.