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