№740000877

*(Д. Статный) Квадрат разлинован на N?N клеток (1 < N < 30). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вверх или вправо. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх - в соседнюю верхнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. На поле имеются зелёные клетки, в которые Робот может зайти, сохранив все накопленные ранее монеты, если перед этим количество собранных монет было чётным, в противном случае, он теряет все собранные монеты и начинает сбор с 0 (монеты, находящиеся в клетке, не идут в счет). Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.

Определите минимальную и максимальную денежные суммы, которые может собрать Робот, пройдя из левой нижней клетки в верхнюю правую.

Исходные данные записаны в файле в виде электронной таблице размером N?N, каждая ячейка которой соответствует клетке квадрата.

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