Задача #2855

(М. Попков) На полигоне для тестирования роботов был установлен квадратный участок размером N x N, в котором каждая клетка содержала монету с денежной суммой от 1 до 100. Робот должен был перемещаться по участку, собирая монеты, но его маршрут заканчивался в одной из угловых клеток — тех, которые были ограничены стенами слева и снизу, включая левую нижнюю клетку поля.

Робот начинал движение из правой верхней клетки квадрата и мог перемещаться только двумя способами:

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

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

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

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