Задача #2699

(М. Попков) На волшебной снежной поляне, разлинованной на N × N клеток (1 < N < 30), живут Герда и Кай. Они собираются отправиться в путешествие по снежному королевству, где каждую клетку поля украшает снежинка с разным количеством волшебных кристаллов (от 1 до 100).

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

Каждый раз, когда Герда и Кай попадают в клетку, они собирают волшебные кристаллы, находящиеся в этой клетке. Это также касается начальной и конечной клеток их маршрута. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами — Герда и Кай не могут продолжать движение, поэтому накопленная сумма кристаллов считается итоговой. Таких конечных клеток может быть несколько, включая правую нижнюю клетку поля.

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

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

Для решения задачи вам предоставляется электронная таблица размером N × N, где каждая ячейка соответствует клетке поля и содержит количество волшебных кристаллов. Внутренние и внешние стены обозначены утолщёнными линиями.