Республиканская олимпиада по информатике 2021 года за 11 класс | Казахстанские олимпиады

Витя - черепашка-ниндзя

Витя готовится стать членом команды нового поколения черепашек-ниндзя. Ему осталось пройти самое важное испытание - решить задачу Донателло.

Донателло дал Вите таблицу состоящую из $n строк и$m$ столбцов. В каждой клетке таблицы написано целое число. Изначально, на клетке в левом верхнем углу таблицы находится фишка. Фишку можно двигать либо на одну клетку вниз либо на одну клетку вправо и только если на соответствующей стороне существует другая клетка. Фишку двигают пока она не окажется на клетке в правом нижнем углу таблицы.

Результатом пути называется сумма чисел на клетках по которым прошла фишка (включая начальную и последнюю клетку). Вите нужно найти путь с максимальным результатом.

Узнав об этом испытании, Леонардо решил что Витя очень легко справится с таким заданием (при его то потенциале). Поэтому, он решил усложнить задачу.

На этот раз, перед тем как двигать фишку, Витя может попросить Леонардо сделать некоторое(возможно нулевое) количество вертикальных и горизонтальных разрезов на таблице своими катанами. Резать можно только по краям клеток и можно считать что катаны Леонардо всегда длиннее сторон таблицы (то есть таблица режется от края до края). В итоге, таблица разделяется на секции. Теперь фишка стоит на левой верхней секции и может двигаться на секцию вниз или на секцию вправо пока не окажется на правой нижней секции. Результатом такого пути называется сумма чисел на клетках секций по которым прошла фишка (включая начальную и последнюю секцию). Помогите Вите разрезать таблицу и найти путь так, чтобы максимизировать результат.

Формат входного файла

В первой строке даны два целых числа $n$ и $m$ $(1 \leq n \leq 1000, 1 \leq m \leq 50)$. В следующих $n$ строках даны по m целых чисел – $j$-тое число на $i$-той строке $a_{i,j} (−10^9 \leq a_{i,j} \leq 10^9)$ является числом на клетке в $i$-той строке и $j$-том столбце таблицы.

Формат выходного файла

Выведите одно целое число – максимальный результат пути которого можно достичь, после совершения некоторого (возможно нулевого) количества разрезов на таблице.

Примеры

Вход

2 2
2000 600
0 4

Выход

2604

Вход

4 5
4 23 -10 -2 3
0 1 7 -3 0
2 3 -3 30 1
4 -17 8 0 5

Выход

78