Есть прямоугольная таблица размером 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 - это может привести к тому, что программа не успеет прочитать входные данные.