Normal MaxSum
Авторы дня думают, что Вам приходилось решать такую задачу: "Есть прямоугольная таблица размером M строк на N столбиков. В каждой клетке записано целое число. По ней нужно пройти сверху вниз, начиная сиз любой клетки верхней строки, дальше каждый раз переходя в одну из "нижних соседних" клеток (иными словами, из клетки с номером (i, j) можно перейти или на (i+1, j-1), или на (i+1, j), или на (i+1, j+1); в случае j = N возможны только 1-й и 2-й из трёх описанных вариантов, в случае j = 1 - только 2-й и 3-й) и закончить маршрут в какой-нибудь клетке нижней строки..."
Пусть добавлено дополнительное ограничение: допускаются только пути, которые проходят (хотя бы по одному разу) через все столбики.
Напишите программу, которая будет находить максимально возможную сумму значений пройденных клеток среди всех допустимых путей.
Входные данные
В первой строке записаны M и N - количество строк и количество столбиков (2 ≤ M ≤ 1024, 2 ≤ N ≤ 768, M ≥ N), дальше в каждой из следующих M строк записано ровно по N разделённых пробелами целых чисел, не превышающих по модулю 10^6 - значения клеток таблицы.
Выходные данные
Выход должен содержать единственное число - максимальную сумму.