Хочу мёда и побольше...
Хочу мёда и побольше...
Миша, как и его мультяшный друг Винни-Пух, очень любил мёд. Поэтому он с нетерпением ждал того момента, когда на пасеке можно будет заняться его сбором. Однако тут возникало несколько проблем, в первую очередь вызванных тем, что сами пчёлы не очень-то любили этот день, когда медведь собирал мёд...
Чтобы пчёлки могли и в дальнейшем приносить мёд и пострадали как можно меньше, да чтобы и он сам был искусан теми же пчёлками поменьше (т.е. медведь не проходил дважды по одному и тому участку пасеки, где расположены улья, из которых уже забран мёд), Миша во время сбора всегда начинал сбор мёда в левом верхнем углу своей пасеки и дальше двигался только вправо и вниз, пока не достигал самого нижнего правого улья, а дальше двигался обратно к началу, но уже передвигался по пасеке только влево и вверх.
Помогите Мише найти маршрут, на котором он соберёт наибольшее количество своего любимого лакомства.
Giriş verilənləri
Входные данные содержат несколько тестовых случаев. Каждый тестовый случай начинается строкой, в которой указано количество ульев на пасеке N (1 < N ≤ 600). Последующие N строк каждого теста задают вес мёда в килограммах, который медведь может взять из расположенного в данной точке пасеки улья. Известно, что пчёлы в каждом из ульев не могли собрать более 100 кг мёда.
Çıxış verilənləri
Для каждого тестового случая выведите оптимальный с точки зрения Миши урожай мёда.
Nümunə
2 10 3 5 10 3 10 3 3 2 5 3 6 7 10 5 1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 5 6 7 8 9
28 46 80