题目描述
有一个 $n$ 行 $m$ 列的网格图，相邻格点之间有边，边有边权。
你可以进行任意次操作，每次操作为使某条边的边权增加 $1$ 。
求一种操作次数最小的方案使得从第一列任意一个点出发到最后一列任意一个点的最短路恰好增加了 $k$ ，输出方案。
输入格式
第一行一个整数 $T$ ，表示数据组数。
对于每一组数据：
第一行三个数 $n,m,k$ ，含义如题目所示。
接下来 $n$ 行，第 $i$ 行包含 $(m-1)$ 个正整数 $r_{i,j}$ ，表示 $(i,j)$ 与 $(i,j+1)$ 之间的边权。
接下来 $(n-1)$ 行，第 $i$ 行包含 $m$ 个正整数 $c_{i,j}$ ，表示 $(i,j)$ 与 $(i+1,j)$ 之间的边权。
输出格式
第一行输出最少的操作次数。
接下来 $n$ 行，第 $i$ 行包含 $(m-1)$ 个正整数 $r_{i,j}'$ ，表示 $(i,j)$ 与 $(i,j+1)$ 之间修改后的边权。
接下来 $(n-1)$ 行，第 $i$ 行包含 $m$ 个正整数 $c_{i,j}'$ ，表示 $(i,j)$ 与 $(i+1,j)$ 之间修改后的边权。
你需要保证 $r_{i,j}', c_{i,j}' \le 2 \times 10^9$ 。
多解输出任意即可。
样例
样例输入 1
1
3 4 6
2 1 15
7 1 9
13 3 2
3 6 1 2
5 2 15 3样例输出 1
9
2 3 15
7 1 10
13 3 4
3 6 3 2
5 4 15 3数据范围
对于 $100\%$ 的数据， $T \le 100, 2 \le n \le 500 ,4 \le nm \le 500,2 \le m \le 500 ,1 \le \sum nm \le 5000 ,1 \le k \le 100 , 1 \le r_{i,j},c_{i,j} \le 10^9$