eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

MaxSum (відвідати усі стовбчики)

MaxSum (відвідати усі стовбчики)

Ліміт часу 2 секунди
Ліміт використання пам'яті 512 MiB

Є прямокутна таблицая розміром N рядків на M стовбчиків. У кожній клітинці записано ціле число. По ній можна пройти зверху вниз, починаючи з довільної клітинки верхнього рядка, далі кожного разу переходячи в одну з "нижніх сусідніх" клітинок (іншими словами, з клітинки під номером (i, j) можна перейти або на (i+1, j-1), або на (i+1, j), або на (i+1, j+1); у випадку j=M останній з трьох описаних варіантів стає неможливим, а у випадку j=1 - перший) і завершити маршрут у якій-небудь клітинці нижнього рядка.

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

Вхідні дані

У першому рядку записані N та M - кількість рядків та кількість стовбчиків (2N1024, 2M768, NM), далі у кожному з наступних N рядків записано рівно M відокремлених пропусками цілих чисел, які не перевищують по модулю 10^6 - значення клітинок таблиці.

Вихідні дані

Вивести єдине число - знайдену максимальну (серед шляхів, які проходять через усі стовбчики) суму.

Примітка: Відповідь дорівнює 28 = 15+5+2+6, тому що усі шляхи з більшою сумою проходять не через усі стовбчики.

Зверніть увагу, що у задачі великий розмір вхідного файлу. На C++ не рекомендується використовувати cin зі включеною синхронвзацією, на java не рекомендується використовувати Scanner - це може призвести до того, що програма не встигне прочитати вхідні дані.

Приклад

Вхідні дані #1
4 3
1 15 2
9 7 5
9 2 4
6 9 -1
Вихідні дані #1
28
Автор Ілля Порубльов
Джерело Літня школа Севастополь 2013, Хвиля 1, День 2