Плити Всесилля#5061
Лорд Бенедикт, тікаючи з замку Чорного Володаря, опиняється у скарбниці Чорної Фортеці. Скарбниця являє собою квадратну кімнату з N \times N клітинок. Бенедикт починає у верхній лівій клітинці, а вихід знаходиться у нижній правій клітинці. Деякі з цих клітинок містять Плити Всесилля. Мета Бенедикта — вибратися з кімнати, пройшовши через якомога більше таких плит. Хоча теоретично він міг би пройти через усі плити, його "Черевички Швидкого Кроку" дозволяють рухатися лише вправо або вниз, тому для вибору шляху йому потрібна стратегія.
У першому рядку знаходиться ціле число (1 \leq N \leq 500). Далі йдуть рядків по цілих чисел у кожному, які описують розташування плит у скарбниці — від верхньої лівої клітинки до нижньої правої. означає порожню клітинку, а — клітинку з Плитою Всесилля. Зверніть увагу, що у верхній лівій і нижній правій клітинках плит немає.
Виведіть максимальну кількість Плит Всесилля, які Бенедикт може пройти на шляху до виходу.
Приклад 1