CF2194E.The Turtle Strikes Back

After a heavy training session, Michelangelo and Raphael decided to order pizza. Today, on the occasion of the holiday, the pizzeria is preparing rectangular pizzas made of $n$ rows and $m$ columns of slices. Each slice has its own unique recipe and flavor.

Michelangelo was the first to open the box and roughly estimated the pleasure of eating each slice: the pleasure from the slice located in the $i$-th row and $j$-th column is equal to $a_{i,j}$. It is guaranteed that there is at least one slice that Michelangelo liked, meaning that among $a_{i, j}$ there is at least one non-negative number.

The turtles agreed that Michelangelo would eat first. According to an ancient tradition, he must choose a route from the top left corner $(1,1)$ to the bottom right corner $(n,m)$ and eat all the slices on that route. In one step, he can move either to the adjacent slice on the right or to the adjacent slice below.

Michelangelo aims to maximize the total pleasure from the eaten slices.

However, Raphael decided to use sauce. Before Michelangelo chooses a route, Raphael decided to choose exactly one slice of pizza and apply his signature sauce to it. But due to the specifics of this sauce, the pleasure from that slice changes to the opposite: if it was previously $a_{i,j}$, after applying the sauce it becomes $-a_{i,j}$.

After that, knowing Raphael's choice, Michelangelo will choose the optimal route for himself and eat all the slices on it.

Raphael became curious about what minimum pleasure Michelangelo could achieve. Help him calculate this number.

经过一场高强度训练后，米开朗基罗和拉斐尔决定点一份披萨。今天恰逢节日，披萨店特制了矩形披萨，由 $n$ 行 $m$ 列的披萨块组成。每一块披萨都有其独特的配方与风味。

米开朗基罗最先打开披萨盒，并粗略估计了每一块披萨带来的愉悦值：位于第 $i$ 行第 $j$ 列的披萨块带来的愉悦值为 $a_{i,j}$。题目保证至少存在一块米开朗基罗喜欢的披萨块，即所有 $a_{i, j}$ 中至少有一个非负数。

两只乌龟约定由米开朗基罗先吃。根据一项古老传统，他必须选择一条从左上角 $(1,1)$ 到右下角 $(n,m)$ 的路径，并吃掉该路径上的所有披萨块。每一步，他只能向右移动到相邻的披萨块，或向下移动到相邻的披萨块。

米开朗基罗的目标是使所吃披萨块的总愉悦值最大化。

然而，拉斐尔决定使用他的特制酱料。在米开朗基罗选定路径之前，拉斐尔将恰好选择一块披萨并为其涂上他的招牌酱料。但由于这种酱料的特殊性质，该块披萨的愉悦值会变为相反数：若原来为 $a_{i,j}$，涂酱后则变为 $-a_{i,j}$。

之后，米开朗基罗在已知拉斐尔的选择的前提下，会选择一条对自己最优的路径，并吃掉该路径上的所有披萨块。

拉斐尔很好奇：米开朗基罗最终所能获得的最小可能愉悦值是多少？请帮助他计算这个数值。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

In the first line of each test case, two integers $n, m\, (1 \le n, m \le 10^6, 1 \leq n \cdot m \le 10^6)$ are given — the number of rows and columns in the table, respectively.

In each of the following $n$ lines of each test case, $m$ integers are provided, separated by spaces. The $j$-th number in the $i$-th of these lines corresponds to the value $a_{i, j}$ ($-10^9 \leq a_{i, j} \leq 10^9$). It is guaranteed that there is at least one non-negative value among the $a_{i, j}$.

It is guaranteed that the sum of $n \cdot m$ across all test cases does not exceed $10^6$

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

For each test case, output a single integer — the minimum pleasure Michelangelo can achieve, which Raphael can guarantee.

对于每个测试用例，输出一个整数——米开朗基罗所能获得的最小愉悦值，该值是拉斐尔能够保证的。

If Raphael did not use the sauce, Michelangelo would choose the path $$ (1,1) \rightarrow (2,1) \rightarrow(3,1) \rightarrow (3,2) \rightarrow (3,3) $$ which gives a total pleasure of $1 + 4 + 1 + 6 - 1 = 11$.

However, if Raphael applies the sauce to the cell $(3,2)$, the value $6$ will turn into $-6$. Then the optimal path for Michelangelo will be $$ (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (3,3) $$ with a total pleasure of $1 - 2 + 3 + 2 - 1 = 3$. Raphael cannot achieve a lower result in any cell

如果拉斐尔不使用酱料，米开朗基罗将选择路径

$$(1,1) \rightarrow (2,1) \rightarrow(3,1) \rightarrow (3,2) \rightarrow (3,3)$$

该路径带来的总愉悦值为 $1 + 4 + 1 + 6 - 1 = 11$。

然而，若拉斐尔将酱料施用于格子 $(3,2)$，其值 $6$ 将变为 $-6$。此时米开朗基罗的最优路径将变为

$$(1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (3,3)$$

该路径带来的总愉悦值为 $1 - 2 + 3 + 2 - 1 = 3$。拉斐尔无法通过在任意其他格子施用酱料来得到更低的结果。