№895493190

(М. Попков) В городе будущего использовались дроны-сборщики, чтобы собирать энергоносители из специального квадрата размером N x N. Однако сбор был осложнён тем, что дроны могли забирать только те элементы, чьё значение было нечётным. Остальные элементы они должны были оставлять на местах. Дрон начинал движение из правой нижней клетки квадрата и завершал свой путь в левой верхней клетке. При этом он мог перемещаться только по следующим правилам:

1) Влево - перемещение в соседнюю клетку, которая находится слева.

2) Вверх - перемещение в соседнюю клетку, которая находится сверху.

Квадрат был окружён внешними стенами, а между клетками могли быть внутренние стены, которые дрон не мог преодолеть. Каждый посещённый дроном элемент с нечётным значением добавлялся к его накоплениям. Это касалось также начальной и конечной клетки маршрута.

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

В ответе укажите два числа - сначала максимальную сумму, затем минимальную.