题目描述

有 $n\times m$ 个点排成 $n$ 行 $m$ 列，相邻点之间被无向带权边连接。

令 $(i,j)$ 表示位于第 $i$ 行第 $j$ 列的点。对于所有 $1\le i,i'\le n$ 和 $1\le j,j'\le m$，当且仅当 $|i-i'|+|j-j'|=1$ 时，$(i,j)$ 与 $(i',j')$ 之间有一条无向边。

堡堡的旅行从第一列的任意一点 $(p,1)$ 出发，在最后一列的任意一点 $(q,m)$ 结束。对于每条边，他都可以沿任意方向通过。

一条路径的距离定义为该路径经过的所有边的边权之和。在所有从第一列到最后一列的路径中，堡堡会选择距离最短的一条，因此旅行距离等于第一列到最后一列的最短路长度。

小青鱼希望堡堡能够多享受一会儿旅程，因此会在堡堡出发前增加一些边的权值。每次操作可以选择任意一条边，将其权值增加 $1$。

小青鱼希望经过若干次操作后，第一列到最后一列的最短路长度恰好增加 $k$。

请计算最少需要进行多少次操作。

本题由原题改编。原题还要求输出一种最优修改方案，本版本只需要输出最少操作次数。

输入格式

有多组测试数据。

第一行输入一个整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行输入三个整数 $n,m,k$，其中 $n$、$m$ 分别表示网格的行数和列数，$k$ 表示要求最短路增加的距离。

接下来 $n$ 行，第 $i$ 行输入 $m-1$ 个整数

$r_{i,1},r_{i,2},\ldots,r_{i,m-1}$，

其中 $r_{i,j}$ 表示连接 $(i,j)$ 与 $(i,j+1)$ 的横向边的权值。

接下来 $n-1$ 行，第 $i$ 行输入 $m$ 个整数

$c_{i,1},c_{i,2},\ldots,c_{i,m}$，

其中 $c_{i,j}$ 表示连接 $(i,j)$ 与 $(i+1,j)$ 的纵向边的权值。

输出格式

对于每组测试数据，输出一行一个整数，表示使第一列到最后一列的最短路长度恰好增加 $k$ 所需的最少操作次数。

输入输出样例 #1

输入 #1

2
3 4 6
2 1 15
7 1 9
13 3 2
3 6 1 2
5 2 15 3
3 3 3
1 1
2 2
3 3
1 1 1
2 2 2

输出 #1

9
4

说明/提示

对于样例中的第一组数据，至少需要进行 $9$ 次操作，才能使第一列到最后一列的最短路长度恰好增加 $6$。

对于样例中的第二组数据，至少需要进行 $4$ 次操作，才能使最短路长度恰好增加 $3$。

数据范围

对于所有测试数据，保证：

• $2\le n,m\le 500$；
• $n\times m\le 500$；
• $1\le k\le 100$；
• $1\le r_{i,j},c_{i,j}\le 10^9$；
• 单个输入文件中所有测试数据的 $n\times m$ 之和不超过 $5\times 10^3$。