eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 64 MiB

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

Input data

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

Output data

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

Examples

Input example #1
2
0 0
0 0
Output example #1
0