Имеется прямоугольная таблица размером строк на столбцов. В каждой клетке записано целое число. По ней можно пройти сверху вниз, начиная из любой клетки верхней строки, дальше каждый раз переходя в одну из "нижних соседних" клеток (иными словами, из клетки с номером можно перейти или на , или на , или на ; в случае последний из трёх описанных вариантов становится невозможным, а в случае — первый) и закончить маршрут в какой-нибудь клетке нижней строки.
Напишите программу, которая будет находить максимально возможную сумму значений пройденных клеток среди всех допустимых путей.
В первой строке записаны и — количество строк и столбцов. Дальше в каждой из следующих строк записано ровно целых чисел (не превышающих по модулю ) — значения клеток таблицы.
Вывести единственное число — найденную максимальную сумму.