\includegraphics{https://static.e-olymp.com/content/aa/aab5f4edb53507cb97ae40eca27fa49d7efe4190.jpg} Мишко, як і його мультяшний друг Вінні-Пух, дуже любив мед. Саме тому він з нетерпінням чекав того моменту, коли на пасіці можна буде зайнятись його збором. Проте тут виникало декілька проблем, у першу чергу викликаних тим, що самі бджоли не дуже любили цей день, коли ведмідь збирав мед... Щоб бджілки могли і у подальшому приносити мед і постраждали якомога менше, да ще й щоб і він сам був покусаний тими ж бджілками поменше (тобто ведмідь не проходив двічі по одній і тій самій ділянці пасіки, де розміщено вулики, з яких вже зібрано мед), Мишко під час збору завжди починав збір меду у лівому верхньому куту своєї пасіки і далі рухався лише праворуч і вниз, доки не досягав самого нижнього правого вулика, а далі рухався назад до початку, але вже пересувався по пасіці лише ліворуч і вгору. Допоможіть Мишку знайти маршрут, на якому він збере найбільшу кількість своїх улюблених ласощів. \InputFile Вхідні дані містять декілька тестових випадків. Кожен тестовий випадок починається рядком, у якому вказано кількість вуликів на пасіці \textbf{N} (\textbf{1} < \textbf{N} ≤ \textbf{600}). Наступні \textbf{N} рядків кожного тесту задають вагу меду в кілограмах, який ведмідь може взяти з розміщеного у даній точці пасіки вулика. Відомо, що бджоли у кожному з вуликів не могли зібрати більше \textbf{100} кг меду. \OutputFile Для кожного тестового випадку виведіть оптимальний з точки зору Мишка врожай меду.