Квадрат разлинован на N × N клеток, где 1 < N < 30. Исполнитель Робот начинает движение в левой верхней клетке и должен попасть в правую нижнюю клетку.
За одно перемещение Робот выполняет одну из двух команд: «вправо» — переходит в соседнюю клетку справа, или «вниз» — переходит в соседнюю клетку снизу. Квадрат ограничен внешними стенами. Между соседними клетками могут находиться внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском в каждой клетке лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает её монету. Это относится и к начальной, и к конечной клетке маршрута.
Рассматриваются только маршруты, заканчивающиеся в правой нижней клетке. Гарантируется, что хотя бы один такой маршрут существует. Определите максимальную и минимальную денежные суммы, которые Робот может собрать на допустимых маршрутах.
Исходные данные представлены электронной таблицей размером N × N; каждая её ячейка соответствует клетке поля. Внутренние и внешние стены обозначены утолщёнными линиями. В ответе запишите сначала максимальную, затем минимальную сумму.
Формат записи ответа
При решении задания в эмуляторе станции КЕГЭ ответ записывается в таблицу справа. Каждое число в отдельную ячейку: первое число записывается в первую ячейку строки, второе - во вторую ячейку строки.
При решении вне станции в строку ответа вводятся два числа в указанном порядке через один пробел.