\begin{problem}{Черепашка наносит ответный удар}{стандартный ввод}{стандартный вывод}{1 секунда}{512 мегабайт}

Участникам, использующим язык \t{Python3}, рекомендуется отправлять решения на проверку с использованием интерпретатора \t{PyPy3}.

\medskip

После тяжёлой тренировки Микеланджело и Рафаэль решили заказать пиццу. Сегодня, по случаю праздника, пиццерия готовит прямоугольные пиццы из $n$ рядов и $m$ колонок, разрезанные на $n \cdot m$ квадратных кусочков. Каждый кусочек имеет свой уникальный рецепт и вкус.

Микеланджело первым открыл коробку и оценил удовольствие от каждого кусочка: удовольствие от куска, находящегося в $i$-м ряду и $j$-м столбце, равно $a_{i,j}$. Понравившиеся куски он оценивает неотрицательными числами, не понравившиеся~--- отрицательными. Гарантируется, что есть хотя бы один кусочек, который понравился Микеланджело, то есть среди $a_{i, j}$ есть хотя бы одно неотрицательное число.

Черепашки договорились, что первым есть будет Микеланджело. По старинной традиции он должен выбрать маршрут от верхнего левого угла $(1,1)$ до нижнего правого угла $(n,m)$ и съесть \textbf{все} кусочки на этом маршруте. За один шаг он может перейти либо в соседний кусок справа, либо в соседний кусок снизу.

Микеланджело стремится максимизировать суммарное удовольствие от съеденных кусочков.

Однако Рафаэль решил воспользоваться соусом.
\textbf{До того} как Микеланджело выберет маршрут, Рафаэль решил выбрать
\textbf{ровно один} кусочек пиццы с неотрицательным значением и нанести на него соус.
К сожалению, Микеланджело не любит этот специфический соус, поэтому удовольствие от этого кусочка меняется на противоположное: если раньше оно было равно $a_{i,j}$, то после соуса становится $-a_{i,j}$.

После этого Микеланджело, зная выбор Рафаэля, выберет оптимальный для себя маршрут и съест все куски на нём.

Рафаэлю стало интересно, какое минимальное удовольствие Микеланджело может получить в зависимости от выбора Рафаэля. Помогите ему, посчитайте это число за него.

\InputFile
В первой строке заданы два целых числа $n$, $m$ ($1 \le n, m \le 10^6$, $1 \leq n \cdot m \le 10^6$)~--- количество строк и столбцов в пицце соответственно.

В каждой из следующих $n$ строк записаны $m$ целых чисел, $j$-e число в $i$-й из этих строк соответствует значению $a_{i, j}$ ($-10^9 \leq a_{i, j} \leq 10^9$).

\OutputFile
Выведите единственное целое число~--- минимальное удовольствие Микеланджело, которое Рафаэль может гарантировать.

Обратите внимание, что ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип \verb|int64| в языке Pascal, тип \verb|long long| в C и C++, тип \verb|long| в Java и C\#). Язык Python будет корректно работать и с типом \verb|int|.

\Scoring
В данной задаче $50$ тестов, помимо тестов из условия, каждый из них оценивается в $2$ балла.
Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, корректно работающие при $n \cdot m \le 5000$, наберут не менее $22$ баллов.

Решения, корректно работающие при $n, m \le 500$, будут наберут не менее $26$ баллов.

\Example

\begin{example}
\exmpfile{example.01}{example.01.a}%
\end{example}

\Note
Если бы Рафаэль не использовал соус, Микеланджело выбрал бы путь
\[
(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$. Ни в какой другой клетке Рафаэль не может добиться меньшего результата для Микеланджело.

\end{problem}

