Задание выполняется с использованием прилагаемых файлов.
Квадрат разлинован на N × N клеток, где 1 < N < 30. Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз.
По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками также могут находиться внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это относится также к начальной и конечной клеткам маршрута.
Робот начинает движение в левой верхней клетке. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, — он не может продолжать движение, поэтому накопленная сумма считается итоговой.
Таких конечных клеток может быть несколько, включая правую нижнюю клетку поля. При разных запусках итоговые накопленные суммы могут различаться.
Определите максимальную и минимальную суммы среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе укажите сначала максимальную, затем минимальную сумму.
Исходные данные представлены электронной таблицей размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями границ ячеек. Обычные тонкие линии стенами не являются.
Иллюстративный пример
Для поля 2 × 2 без внутренних стен с числами, приведёнными ниже, возможны маршруты 1 → 2 → 4 и 1 → 3 → 4.
Максимальная сумма в этом примере равна 8, минимальная — 7. Пример поясняет правила подсчёта; для выполнения задания используйте данные прилагаемого файла.
Запись ответа на платформе. Введите два числа в указанном в условии порядке, разделив их одним пробелом.