`Всеукраїнський центр проведення олімпіад в мережі Інтернет
  1. Maxsum

 Задача Maxsum
          
Жюри думает, что вам приходилось решать такую задачу:
«Имеется  прямоугольная таблица размером M строк на N столбцов. В каждой клеточке записано целое число. По ней нужно пройти сверху вниз, начав путь в какой-либо клеточке верхней строки, дальше каждый раз переходя в одну из «нижне-соседних» клеточек (другими словами, из клеточки с номером (i, j) можно перейти или к (i+1, j–1), или к (i+1, j), или к (i+1, j+1); в случае j=N возможные лишь 1-й и 2-й из трех перечисленных вариантов, в случае j=1 — лишь 2-й и 3-й) и закончить маршрут в какой-либо клеточке нижней строки. 
          Напишите программу, которая будет находить максимально возможную сумму значений пройденных клеточек среди всех допустимых путей»
            Решите  данную задачу при дополнительном ограничении: допускаются лишь пути, которые проходят (хотя бы по одному разу) через все столбики
.
Технические условия
Программа Maxsum читает с клавиатуры M и N  количество строк и количество столбцов (2≤M≤200, 2≤N≤40, M>=N), далее в каждой из последующих M строк считывается ровно по N разделенных пробелами целых чисел (каждое не превышает по модулю 1 000 000) — значения клеточек таблицы. Программа выводит на экран единственное число – искомую величину.
Пример 

Ввод

Вывод 
4 3
1 15 2
9 7 5
9 2 4
6 9 –1 		 28
         





© LIKT 1998-2024