eolymp
bolt
Try our new interface for solving problems
Məsələlər

Хочу мёда и побольше...

Хочу мёда и побольше...

Zaman məhdudiyyəti 5 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Миша, как и его мультяшный друг Винни-Пух, очень любил мёд. Поэтому он с нетерпением ждал того момента, когда на пасеке можно будет заняться его сбором. Однако тут возникало несколько проблем, в первую очередь вызванных тем, что сами пчёлы не очень-то любили этот день, когда медведь собирал мёд...

Чтобы пчёлки могли и в дальнейшем приносить мёд и пострадали как можно меньше, да чтобы и он сам был искусан теми же пчёлками поменьше (т.е. медведь не проходил дважды по одному и тому участку пасеки, где расположены улья, из которых уже забран мёд), Миша во время сбора всегда начинал сбор мёда в левом верхнем углу своей пасеки и дальше двигался только вправо и вниз, пока не достигал самого нижнего правого улья, а дальше двигался обратно к началу, но уже передвигался по пасеке только влево и вверх.

Помогите Мише найти маршрут, на котором он соберёт наибольшее количество своего любимого лакомства.

Giriş verilənləri

Входные данные содержат несколько тестовых случаев. Каждый тестовый случай начинается строкой, в которой указано количество ульев на пасеке N (1 < N600). Последующие N строк каждого теста задают вес мёда в килограммах, который медведь может взять из расположенного в данной точке пасеки улья. Известно, что пчёлы в каждом из ульев не могли собрать более 100 кг мёда.

Çıxış verilənləri

Для каждого тестового случая выведите оптимальный с точки зрения Миши урожай мёда.

Nümunə

Giriş verilənləri #1
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
Çıxış verilənləri #1
28
46
80
Mənbə Командный Кубок Украины 2011 - школьники - тур 1