Максимальная сумма базовая
Максимальная сумма базовая
Имеется прямоугольная таблица размером n строк на m столбцов. В каждой клетке записано целое число. По ней можно пройти сверху вниз, начиная из любой клетки верхней строки, дальше каждый раз переходя в одну из "нижних соседних" клеток (иными словами, из клетки с номером (i, j) можно перейти или на (i + 1, j - 1), или на (i + 1, j), или на (i + 1, j + 1); в случае j = m последний из трёх описанных вариантов становится невозможным, а в случае j = 1 — первый) и закончить маршрут в какой-нибудь клетке нижней строки.
Напишите программу, которая будет находить максимально возможную сумму значений пройденных клеток среди всех допустимых путей.
Входные данные
В первой строке записаны n и m~(1 \le n, m \le 200) — количество строк и столбцов. Дальше в каждой из следующих n строк записано ровно m целых чисел (не превышающих по модулю 10^6) — значения клеток таблицы.
Выходные данные
Вывести единственное число — найденную максимальную сумму.
Пример
4 3 1 15 2 9 7 5 9 2 4 6 9 -1
42