Є прямокутна таблиця розміром рядків на стовбчиків. У кожній клітинці записано ціле число. По ній можна пройти зверху вниз, починаючи з довільної клітинки верхнього рядка, далі кожного разу переходячи в одну з "нижніх сусідніх" клітинок (іншими словами, з клітинки під номером можна перейти або на , або на , або на ; у випадку останній з трьох описаних варіантів стає неможливим, а у випадку — перший) і завершити маршрут у якій-небудь клітинці нижнього рядка.
Напишіть програму, яка буде знаходити максимально можливу суму значень пройдених клітинок серед усіх допустимих шляхів.
У першому рядку записані та — кількість рядків та кількість стовбчиків, далі у кожній з наступних рядків записано рівно цілих чисел (кожне не перевищує по модулю ) — значення клітинок таблиці.
Вивести єдине число — знайдену максимальну суму.