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