Rikka with K-Match

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

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

Now Yuta wants to calculate the minimum weight $K$-matching of $G$.

It is too difficult for Rikka. Can you help her?  

An edge set $S$ is a match of $G=\langle V,E \rangle$ if and only if each nodes in $V$ connects to at most one edge in $S$. A match $S$ is a $K$-match if and only if $|S|=K$. The weight of a match $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$-match of $G$ with the minimum weight.

The first line contains a number $t(1 \leq t \leq 1000)$, the number of the testcases. And there are no more than $3$ testcases with $n > 100$.

For each testcase, the first line contains three numbers $n,m,K(1 \leq n \leq 4 \times 10^4,1 \leq m \leq 4),1 \leq K \leq \lfloor \frac{nm}{2} \rfloor$.

Then $n-1$ lines follow, each line contains $m$ numbers $A_{i,j}(1 \leq A_{i,j}
\leq 10^9)$ -- the weight of the edge between $(i,j)$ and $(i+1,j)$.

If $m>1$, then $n$ lines follow, each line contains $m-1$ numbers $B_{i,j}(1 \leq B_{i,j} \leq 10^9)$ -- the weight of the edge between $(i,j)$ and $(i,j+1)$.

For each testcase, print a single line with a single number -- the answer.

It is guaranteed that there exists at least one $K$-match.

3
3 3 1
3 4 5
8 9 10
1 2
6 7
11 12
3 3 2
3 4 5
8 9 10
1 2
6 7
11 12
3 3 3
3 4 5
8 9 10
1 2
6 7
11 12

1
5
12

2017 Multi-University Training Contest - Team 5