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