← 返回题目列表

Codeforces · 2194/E

E. 乌龟的反击

中文机器翻译题面 查看原题

经过高强度的训练后,米开朗基罗和拉斐尔决定点披萨。今天,在节日之际,披萨店正在准备由 $$$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$$$

输出

对于每个测试用例,输出一个整数 - 米开朗基罗可以实现的最小乐趣,拉斐尔可以保证。

示例

输入
复制

2
3 3
1 -2 3
4 -5 2
1 6 -1
2 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$$$。拉斐尔在任何细胞中都无法获得较低的结果