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