CF2194E The Turtle Strikes Back

在一次艰苦的训练之后，Michelangelo 和 Raphael 决定点披萨庆祝。今天因为节日，披萨店准备了由 $n$ 行 $m$ 列切片组成的矩形披萨。每片披萨都有独特的配方和风味。 Michelangelo 是第一个打开盒子的人，他粗略估算了每片披萨的享受值：位于第 $i$ 行第 $j$ 列的披萨片带来的享受值为 $a_{i,j}$。保证至少有一片披萨是 Michelangelo 喜欢的，即 $a_{i,j}$ 中至少有一个非负数。 两只乌龟约定由 Michelangelo 先吃。按照古老的传统，他必须从左上角 $(1,1)$ 走到右下角 $(n,m)$，并吃掉这条路径上的所有披萨片。每一步，他只能向右或向下走到相邻的披萨片。 Michelangelo 希望最大化他吃到的总享受值。 然而 Raphael 决定使用特制酱汁。在 Michelangelo 选择路径之前，Raphael 决定选择恰好一片披萨，并在上面涂抹他独家秘制的酱汁。但是由于这种酱汁特殊，这片披萨的享受值会变为相反数：即原来是 $a_{i,j}$，使用酱汁后变为 $-a_{i,j}$。 之后，Michelangelo 知道 Raphael 的选择后，将为自己选择最优路径，吃掉这条路径上的所有披萨片。 Raphael 很好奇 Michelangelo 最少能够获得多少享受值。请帮助他计算这个最小值。

每个测试点包含多个测试用例。第一行包含测试用例数 $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$。

对于每个测试用例，输出一个整数，表示 Raphael 能保证的 Michelangelo 最少能获得的享受值。

如果 Raphael 不使用酱汁，Michelangelo 会选择如下路径： $$ (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$。此时 Michelangelo 的最优路径为： $$ (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (3,3) $$ 获得的总享受值为 $1 - 2 + 3 + 2 - 1 = 3$。在其他任何单元格上使用酱汁，Raphael 都无法获得更低的结果。 由 ChatGPT 5 翻译