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