Динамическое программирование в электронных таблицах

Квадрат украшен новогодними огоньками и разбит на N × N клеток (1 < N < 30). По нему перемещается Робот‑Снеговик, выполняя за одно действие одну из двух команд: вправо или вниз.

По команде вправо Робот‑Снеговик переходит в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю.

Квадрат окружён внешними стенами. Между соседними клетками также могут находиться внутренние стены. Через стену Робот пройти не может.

В «угловых» клетках поля (тех, которые справа и снизу ограничены стенами) Робот не может продолжить путь. Таких конечных клеток на поле может быть несколько, включая правую нижнюю клетку.

Перед запуском Робот‑Снеговик имеет запас энергии, равный 825. Расход энергии на прохождение каждой клетки, включая стартовую и финальную, равен числу, записанному в этой клетке. Если энергии Робота недостаточно, чтобы сделать следующий шаг, то он останавливается.

Задание 1

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

Задание 2

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

Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.

В ответе укажите два числа: количество конечных клеток и минимальный запас энергии.

Пример входных данных