Квадрат разлинован
NxN клеток (1 <
N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд:
вправо или
вверх. По команде
вправо Робот перемещается в соседнюю правую клетку, по команде
вверх - в соседнюю верхнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стены Робот пройти не может.
Перед каждым запуском Робота он обладает запасом энергии в 5000 единиц. При перемещении Робот тратит такое количество энергии, которое указано в той клетке, куда Робот перемещается. Это также относится к начальной и конечной клеткам маршрута Робота.
В "угловых" клетках поля - тех, которые справа и сверху ограничены стенами, Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую верхнюю клетку поля. При разных запусках итоговые накопленные суммы могут отличаться.
Определите минимальный и максимальный запас энергии, среди всех итоговых запасов, которые могут остаться у Робота при перемещении из левой нижней клетки квадрата в его правую верхнюю клетку. В ответе укажите два числа: сначала минимальный запас, затем максимальный.
Файл к заданию