Rikka with K-Match

Problem Description

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.

Input

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)$.

Output

For each testcase, print a single line with a single number -- the answer. It is guaranteed that there exists at least one $K$-match.

Sample Input

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

Sample Output

1
5
12

Source

2017 Multi-University Training Contest - Team 5

https://acm.hdu.edu.cn/showproblem.php?pid=6094