E. Черепашка наносит ответный удар
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После тяжёлой тренировки Микеланджело и Рафаэль решили заказать пиццу. Сегодня, по случаю праздника, пиццерия готовит прямоугольные пиццы из $$$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$$$ целых чисел, разделённых пробелами. $$$j$$$-е число в $$$i$$$-й из этих строк соответствует значению $$$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$$$.

Однако, если Рафаэль нанесёт соус на клетку $$$(3,2)$$$, значение $$$6$$$ превратится в $$$-6$$$. Тогда оптимальным для Микеланджело станет путь $$$$$$ (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (3,3) $$$$$$ с суммарным удовольствием $$$1 - 2 + 3 + 2 - 1 = 3$$$. Ни в одной клетке Рафаэль не может добиться меньшего результата.