K-매칭

그래프 $G$를 생각하자. 이 그래프에는 $n \cdot m$개의 정점 $(i, j)$ ($1 \leq i \leq n$, $1 \leq j \leq m$)가 있다. 두 정점 $(a, b)$와 $(c, d)$ 사이에 간선이 있는 것은 $|a - c| + |b - d| = 1$일 때뿐이다. 각 간선에는 가중치가 있다.

$G$의 $K$-매칭 중 최소 가중치를 구하라.

간선 집합 $S$가 $G = \langle V, E \rangle$의 매칭이라는 것은 $V$의 각 정점이 $S$의 간선 중 최대 하나에 연결되어 있다는 뜻이다. 매칭 $S$가 $|S| = K$를 만족하면 $S$는 $K$-매칭이다. 매칭 $S$의 가중치는 $S$에 속한 간선 가중치의 합이다. $G$의 최소 가중치 $K$-매칭은 가중치가 가장 작은 $K$-매칭이다.

첫 줄에 테스트 케이스의 수 $t$가 주어진다 ($1 \leq t \leq 1000$). $n > 100$인 테스트 케이스는 최대 3개이다.

각 테스트 케이스의 첫 줄에는 정수 $n$, $m$, $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$).

이어서 $n - 1$개의 줄이 주어지며, 각 줄에는 정수 $m$개 $A_{i, j}$가 있다. 이는 $(i, j)$와 $(i + 1, j)$ 사이 간선의 가중치이다 ($1 \leq A_{i, j} \leq 10^9$).

$m > 1$이면 추가로 $n$개의 줄이 주어지며, 각 줄에는 정수 $m - 1$개 $B_{i, j}$가 있다. 이는 $(i, j)$와 $(i, j + 1)$ 사이 간선의 가중치이다 ($1 \leq B_{i, j} \leq 10^9$).

각 테스트 케이스마다 최소 가중치를 한 줄에 출력한다.