经过高强度的训练后,米开朗基罗和拉斐尔决定点披萨。今天,在节日之际,披萨店正在准备由 $$$n$$$ 行和 $$$m$$$ 列切片制成的矩形披萨。每片都有其独特的配方和风味。
米开朗基罗是第一个打开盒子的人,粗略地估计了吃每一片的乐趣:位于第$$$i$$$行第$$$j$$$列的切片的乐趣等于$$$a_{i,j}$$$。保证至少有一个切片是米开朗基罗喜欢的,也就是说$$$a_{i, j}$$$中至少有一个非负数。
海龟们同意米开朗基罗先吃。根据一个古老的传统,他必须选择一条从左上角$$$(1,1)$$$到右下角$$$(n,m)$$$的路线并吃饭 全部 该路线上的切片。在一步中,他可以移动到右侧的相邻切片或下方的相邻切片。
米开朗基罗的目标是最大限度地提高食用切片的总体乐趣。
然而,拉斐尔决定使用酱汁。 之前 米开朗基罗选择一条路线,拉斐尔决定选择 正好一个 一片披萨并涂上他的招牌酱。但由于这种酱汁的特殊性,那片切片的乐趣发生了相反的变化:如果之前是$$$a_{i,j}$$$,那么在涂上酱汁后,它就变成了$$$-a_{i,j}$$$。
之后,米开朗基罗知道拉斐尔的选择后,会选择最适合自己的路线,并吃掉上面所有的切片。
拉斐尔开始好奇米开朗基罗能获得什么最低限度的快乐。帮他算一下这个数字。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
在每个测试用例的第一行,给出两个整数 $$$n, m\, (1 \le n, m \le 10^6, 1 \leq n \cdot m \le 10^6)$$$ - 分别表示表中的行数和列数。
在每个测试用例的以下 $$$n$$$ 行中,提供了 $$$m$$$ 个整数,并用空格分隔。这些行中第 $$$i$$$ 中的第 $$$j$$$ 数字对应于值 $$$a_{i, j}$$$ ($$$-10^9 \leq a_{i, j} \leq 10^9$$$)。保证$$$a_{i,j}$$$中至少有一个非负值。
保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$10^6$$$
输出
对于每个测试用例,输出一个整数 - 米开朗基罗可以实现的最小乐趣,拉斐尔可以保证。
示例
输入复制
23 31 -2 34 -5 21 6 -12 4-1 -1 -1 1-1 -1 -1 -1
输出复制
3-5
注意
如果拉斐尔不使用酱料,米开朗基罗会选择路径 $$(1,1) \rightarrow (2,1) \rightarrow(3,1) \rightarrow (3,2) \rightarrow (3,3)$$,这会带来 $$$1 + 4 + 1 + 6 - 1 = 11$$$ 的总乐趣。
但是,如果 Raphael 将酱汁涂抹到单元格 $$$(3,2)$$$ 上,则值 $$$6$$$ 将变为 $$$-6$$$。那么米开朗基罗的最佳路径将是 $$(1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (3,3)$$,总的乐趣为 $$$1 - 2 + 3 + 2 - 1 = 3$$$。拉斐尔在任何细胞中都无法获得较低的结果