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