eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Имеется прямоугольная таблица размером 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) — значения клеток таблицы.

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

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

Пример

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