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

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

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

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

Примеры