e-olymp
Задачи

Максимальная сумма базовая

Максимальная сумма базовая

Имеется прямоугольная таблица размером n строк на m столбцов. В каждой клетке записано целое число. По ней можно пройти сверху вниз, начиная из любой клетки верхней строки, дальше каждый раз переходя в одну из "нижних соседних" клеток (иными словами, из клетки с номером (i, j) можно перейти или на (i + 1, j - 1), или на (i + 1, j), или на (i + 1, j + 1); в случае j = m последний из трёх описанных вариантов становится невозможным, а в случае j = 1 - первый) и закончить маршрут в какой-нибудь клетке нижней строки.

Напишите программу, которая будет находить максимально возможную сумму значений пройденных клеток среди всех допустимых путей.

Входные данные

В первой строке записаны n и m (1n, m200) - количество строк и столбцов. Дальше в каждой из следующих n строк записано ровно m целых чисел (не превышающих по модулю 106) - значения клеток таблицы.

Выходные данные

Вывести единственное число - найденную максимальную сумму.

Лимит времени 1 секунды
Лимит использования памяти 128 MiB
Входные данные #1
4 3
1 15 2
9 7 5
9 2 4
6 9 -1
Выходные данные #1
42
Автор Илья Порублёв
Источник Летняя школа Севастополь 2013, Волна 1, День 2