被 hack 的题解：

@asuldb：https://www.luogu.com.cn/blog/asuldb/solution-p5038

@jijidawang：https://www.luogu.com.cn/blog/writeSTL/solution-p5038

以上题解的问题都是错误地输出了 $-1$。

另外此题的数据范围有误，应为小于等于 $10^9$，assert(a[i][j] < 1000000000) 会 RE，assert(a[i][j] <= 1000000000) 则不会。

数据没改 \r\n 的问题。

输入：

1
40 40
0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0
1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0
0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0
1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 1000000000
0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 1000000000 0
1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 1000000000 0 1000000000
0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 1000000000 0 1000000000 0
1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 1000000000 0 1000000000 0 1000000000
0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 1000000000 0 1000000000 0 1000000000 0
1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000
0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0
1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000
0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0
1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000
0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0
1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000
0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0
1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000
0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0
1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000
0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0
1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000
0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0
1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000
0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0
1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000
0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0
1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000
0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0
1000000000 0 1000000000 0 1000000000 0 1000000000 0 0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000
0 1000000000 0 1000000000 0 1000000000 0 0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0
1000000000 0 1000000000 0 1000000000 0 0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000
0 1000000000 0 1000000000 0 0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0
1000000000 0 1000000000 0 0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000
0 1000000000 0 0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0
1000000000 0 0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000
0 0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0
0 0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000
0 0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0
0 0 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000

输出：

14839000000000