Хочу мёда и побольше...
Миша, как и его мультяшный друг Винни-Пух, очень любил мёд. Поэтому он с нетерпением ждал того момента, когда на пасеке можно будет заняться его сбором. Однако тут возникало несколько проблем, в первую очередь вызванных тем, что сами пчёлы не очень-то любили этот день, когда медведь собирал мёд...
Чтобы пчёлки могли и в дальнейшем приносить мёд и пострадали как можно меньше, да чтобы и он сам был искусан теми же пчёлками поменьше (т.е. медведь не проходил дважды по одному и тому участку пасеки, где расположены улья, из которых уже забран мёд), Миша во время сбора всегда начинал сбор мёда в левом верхнем углу своей пасеки и дальше двигался только вправо и вниз, пока не достигал самого нижнего правого улья, а дальше двигался обратно к началу, но уже передвигался по пасеке только влево и вверх.
Помогите Мише найти маршрут, на котором он соберёт наибольшее количество своего любимого лакомства.
Входные данные
Входные данные содержат несколько тестовых случаев. Каждый тестовый случай начинается строкой, в которой указано количество ульев на пасеке N (1 < N ≤ 600). Последующие N строк каждого теста задают вес мёда в килограммах, который медведь может взять из расположенного в данной точке пасеки улья. Известно, что пчёлы в каждом из ульев не могли собрать более 100 кг мёда.
Выходные данные
Для каждого тестового случая выведите оптимальный с точки зрения Миши урожай мёда.