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