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