eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Плиты Всемогущества

Плиты Всемогущества

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Лорд Бенедикт, спасаясь из замка Черного Властелина, вбегает прямиком в сокровищницу его Черной Крепости. Сокровищница представляет из себя квадратный зал размером N×N клеточек, Бенедикт находится в левой верхней клеточке зала, выход – в правой нижней. В некоторых клеточках зала находятся Плиты Всемогущества. Бенедикту следует выбраться из зала, попутно пройдя через как можно большее количество Плит Всемогущества. Он мог бы посетить все, но с утра герой одел "Башмаки Быстроступы", которые позволяют ему двигаться только вправо или вниз, так что придется выбирать оптимальный маршрут.

Входные данные

В первой строке задано число N (1N500). В следующих N строках находится по N чисел, описывающих сокровищницу, начиная с левой верхней клеточки и заканчивая правой нижней. Число 0 соответствует пустой клеточке, число 1 – клеточке с Плитой. В верхней левой и правой нижней клеточках плит нет.

Выходные данные

Выведите максимальное количество Плит Всемогущества, через которые может пройти Бенедикт.

Пример

Входные данные #1
2
0 0
0 0
Выходные данные #1
0