MaxSum (відвідати усі стовбчики)
Є прямокутна таблицая розміром N рядків на M стовбчиків. У кожній клітинці записано ціле число. По ній можна пройти зверху вниз, починаючи з довільної клітинки верхнього рядка, далі кожного разу переходячи в одну з "нижніх сусідніх" клітинок (іншими словами, з клітинки під номером (i, j) можна перейти або на (i+1, j-1), або на (i+1, j), або на (i+1, j+1); у випадку j=M останній з трьох описаних варіантів стає неможливим, а у випадку j=1 - перший) і завершити маршрут у якій-небудь клітинці нижнього рядка.
Напишіть програму, яка буде знаходити максимально можливу суму значень пройдених клітинок серед усіх допустимих шляхів, які проходять хоча б по одному разу через кожен зі стовбчиків.
Вхідні дані
У першому рядку записані N та M - кількість рядків та кількість стовбчиків (2 ≤ N ≤ 1024, 2 ≤ M ≤ 768, N ≥ M), далі у кожному з наступних N рядків записано рівно M відокремлених пропусками цілих чисел, які не перевищують по модулю 10^6 - значення клітинок таблиці.
Вихідні дані
Вивести єдине число - знайдену максимальну (серед шляхів, які проходять через усі стовбчики) суму.
Примітка: Відповідь дорівнює 28 = 15+5+2+6, тому що усі шляхи з більшою сумою проходять не через усі стовбчики.
Зверніть увагу, що у задачі великий розмір вхідного файлу. На C++ не рекомендується використовувати cin зі включеною синхронвзацією, на java не рекомендується використовувати Scanner - це може призвести до того, що програма не встигне прочитати вхідні дані.