18_0273

Задание выполняется с использованием прилагаемого файла.

Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот начинает путь в левой верхней клетке и заканчивает его в правой нижней. За одно перемещение Робот может перейти в соседнюю клетку вправо или вниз.

В каждой клетке записано число от 1 до 22. При переходе в очередную клетку Робот забирает монету тогда и только тогда, когда число в этой клетке чётное и строго больше числа в непосредственно предыдущей клетке пути. Сравниваются числа, записанные в клетках, независимо от того, забирал ли Робот монету в предыдущей клетке. Достоинство монеты равно числу, записанному в клетке. В начальной клетке монету не берут, так как перед ней нет предыдущей клетки.

Определите максимальную и минимальную суммы, которые может собрать Робот. В ответе укажите два числа: сначала максимальную сумму, затем минимальную.

Данные находятся в электронной таблице размером $N \times N$, каждая ячейка которой соответствует клетке квадрата.

Пример поля

Файл к заданию:

• 18_0273.ods