Problems
Normal MaxSum
Normal MaxSum
Авторы дня думают, что Вам приходилось решать такую задачу: "Есть прямоугольная таблица размером \textbf{M} строк на \textbf{N} столбиков. В каждой клетке записано целое число. По ней нужно пройти сверху вниз, начиная сиз любой клетки верхней строки, дальше каждый раз переходя в одну из "нижних соседних" клеток (иными словами, из клетки с номером (\textbf{i}, \textbf{j}) можно перейти или на (\textbf{i}+\textbf{1}, \textbf{j}-\textbf{1}), или на (\textbf{i}+\textbf{1}, \textbf{j}), или на (\textbf{i}+\textbf{1}, \textbf{j}+\textbf{1}); в случае \textbf{j} = \textbf{N} возможны только \textbf{1}-й и \textbf{2}-й из трёх описанных вариантов, в случае \textbf{j} = \textbf{1} - только \textbf{2}-й и \textbf{3}-й) и закончить маршрут в какой-нибудь клетке нижней строки..."
Пусть добавлено дополнительное ограничение: допускаются только пути, которые проходят (хотя бы по одному разу) через все столбики.
Напишите программу, которая будет находить максимально возможную сумму значений пройденных клеток среди всех допустимых путей.
\InputFile
В первой строке записаны \textbf{M} и \textbf{N} - количество строк и количество столбиков (\textbf{2} ≤ \textbf{M} ≤ \textbf{1024}, \textbf{2} ≤ \textbf{N} ≤ \textbf{768}, \textbf{M} ≥ \textbf{N}), дальше в каждой из следующих \textbf{M} строк записано ровно по \textbf{N} разделённых пробелами целых чисел, не превышающих по модулю \textbf{10^6} - значения клеток таблицы.
\OutputFile
Выход должен содержать единственное число - максимальную сумму.
Input example #1
4 3 1 15 2 9 7 5 9 2 4 6 9 -1
Output example #1
28