Є прямокутна таблиця розміром ~N~ рядків на ~M~ стовпчиків. У кожній клітинці записане невід'ємне ціле число. По ній потрібно пройти згори донизу, починаючи з будь-якої клітинки верхнього рядка, далі переходячи щоразу в одну з «нижньо-сусідніх» і закінчити маршрут у якій-небудь клітинці нижнього рядка. «Нижньо-сусідня» означає, що з клітинки ~(i,j)~ можна перейти в ~{(i+1, j-1)}~, або в ~{(i+1,j)}~, або в ~{(i+1,j+1)}~, але не виходячи за межі таблиці (у крайньому лівому стовпчику перший з наведених варіантів стає неможливим, а у крайньому правому – останній).

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

Вхідні дані

У першому рядку записані ~N~ та ~M~ – кількість рядків і кількість стовпчиків (~1\leqslant N,\,M\leqslant 200~); далі у кожному з наступних ~N~ рядків записано рівно по ~M~ розділених пробілами цілих чисел, абсолютні значення (модулі) яких не перевищують ~10^6~ (мільйона) – значення клітинок.

Результати

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

Приклади

Вхід

4 3
1 15 2
9 7 5
9 2 4
6 9 -1

Результат

42

Примітка

~42 = 15 + 9 + 9 + 9~.