Задание 18 ЕГЭ по информатике

Квадрат разлинован на $N * N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из трех команд: вправо, вниз и вправо вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз – в соседнюю нижнюю; выполняя команду вправо вниз робот перемещается на одну клетку вправо и одну вниз, делая перемещение по диагонали. Исключением являются клетки, отмеченные желтым цветом. Находясь в них, робот может выполнять только команду вправо вниз.

Перед запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке – это натуральное число, не превышающее 100. Это правило относится к начальной и конечной клеткам маршрута Робота.

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

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

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

Пример входных данных

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/2711_18.xls