Задание выполняется с использованием прилагаемого файла
Квадрат разлинован на N × N клеток (1 < N < 30). Робот-сборщик монет находится в левой верхней клетке. Он может перемещаться в соседнюю клетку вправо или вниз (одно из двух действий за один шаг). Между соседними клетками квадрата также могут быть внутренние стены (обозначены жирными линиями). Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Робот перемещается из клетки в клетку и собирает монеты в клетках, через которые он проходит. Пройденная клетка учитывается один раз, включая стартовую.
В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами или краем поля, — Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку.
Определите максимальную и минимальную денежные суммы среди всех возможных итоговых сумм, которые Робот мог бы набрать, дойдя до любой из конечных клеток.
В ответе запишите сначала максимальную, затем минимальную сумму через пробел.