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