Квадрат разлинован на N×N клеток (1 <, N <, 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из трех команд: вправо, вниз или вправо_сквозь_стену. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю, команду вправо_сквозь_стену робот может выполнять, только находясь на голубых клеток, и перемещается вправо на одну клетку сквозь стену. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может, за исключением голубых клеток.
Перед запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки, включая голубые. Размер бонуса в каждой клетке – это натуральное число, не превышающее 700. Это правило относится к начальной и конечной клеткам маршрута Робота.
Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. В ответе укажите два числа: сначала минимальную сумму, затем максимальную.
Для Вашего удобства исходные данные для Робота записаны в виде прямоугольной таблицы в файлах с тремя расширениями, каждая ячейка которой соответствует клетке квадрата.
Пример входных данных:
Для указанных входных данных ответом является пара чисел: 760 1150.
