Хочу піци й чим побільше...#1299
Мікеланджело, як і всі його брати-черепашки-ніндзя, дуже любив піцу. Саме тому він з нетерпінням чекав моменту, коли зможе почати збирати піцу в піцерії. Однак цей день приніс кілька проблем, головним чином тому, що піцайоло не подобалося, коли черепашка забирала занадто багато піци...
Щоб піцайоло міг і надалі готувати піцу і щоб не створювати йому зайвих проблем, а також щоб самому не розлютити його надто сильно (тобто черепашка ніколи не проходить двічі по одній і тій самій клітинці піцерії, з якої вже зібрано піцу), Мікеланджело завжди починає збирати піцу з верхнього лівого кута піцерії і рухається лише вправо та вниз, поки не дійде до правої нижньої коробки. Потім він повертається у вихідну точку, рухаючись лише вліво й вгору.
Допоможіть Мікеланджело знайти маршрут, який дозволить йому зібрати максимально можливу кількість його улюблених ласощів.
Вхідні дані містять кілька тестових випадків. Кожен тестовий випадок починається з рядка, що вказує кількість коробок з піцою в піцерії (1 < N \leq 600). Далі для кожного тестового випадку йде рядків, у кожному з яких зазначено кількість шматків піци, які черепашка може взяти з коробки, що знаходиться у цій позиції піцерії. Відомо, що в кожній коробці не може бути більше шматків піци.
Для кожного тестового випадку виведіть оптимальну кількість шматків піци, яку Мікеланджело зможе зібрати.
Приклад 1