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