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

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

Вихідні дані

Виведіть єдине число — знайдену максимальну суму.

Приклади