考虑一个包含 $n \cdot m$ 个节点 $(i, j)$ ($1 \le i \le n, 1 \le j \le m$) 的图 $G$。当且仅当 $|a - c| + |b - d| = 1$ 时，节点 $(a, b)$ 和 $(c, d)$ 之间存在一条边。每条边都有一个权重。

计算图 $G$ 中 $K$-匹配的最小权重。

边集 $S$ 是图 $G = \langle V, E \rangle$ 的一个匹配，当且仅当 $V$ 中的每个节点在 $S$ 中至多连接一条边。如果 $|S| = K$，则称匹配 $S$ 为 $K$-匹配。匹配 $S$ 的权重是 $S$ 中所有边的权重之和。$G$ 的最小权重 $K$-匹配定义为权重最小的 $K$-匹配。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量 ($1 \le t \le 1000$)。保证 $n > 100$ 的测试用例不超过 3 个。

对于每个测试用例，第一行包含三个整数 $n, m$ 和 $K$ ($1 \le n \le 4 \cdot 10^4, 1 \le m \le 4, 1 \le K \le \lfloor \frac{n \cdot m}{2} \rfloor$)。

接下来 $n - 1$ 行，每行包含 $m$ 个整数 $A_{i,j}$，表示节点 $(i, j)$ 和 $(i + 1, j)$ 之间边的权重 ($1 \le A_{i,j} \le 10^9$)。

如果 $m > 1$，则接下来还有 $n$ 行，每行包含 $m - 1$ 个整数 $B_{i,j}$，表示节点 $(i, j)$ 和 $(i, j + 1)$ 之间边的权重 ($1 \le B_{i,j} \le 10^9$)。

输出格式

对于每个测试用例，输出一行，包含一个整数：所需的最小权重。

样例

输入 1

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

1
5
12