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