eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Стек куль

Стек куль

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Телеканал XYZ розробляє нове ігрове шоу, у якому участники повинні зробити деякий вибір щоб отримати приз. Гра складається з трикутного стека куль, на кожній з яких записано цілочисельне значення, як показано нижче на прикладі.

Участник повинен вибрати набір куль, і його призом будет сума чисел на них. Участник може взяти кулю, лише якзо він берет усі кулі, які знаходять безпосередньо над нею. Це может вимагати зняття додаткових куль за описаним правилом. Участник може не брати жодної кулі, у такому випадку його приз буде рівним нулю.

Директор телешоу зацікавлений у тому, щоб участник отримав максимальний приз для заданого стеку. Так як він є Вашим босом, то попросив Вас розв'язати цю задачу.

Вхідні дані

Кожен тест задається у декількох рядках. Перший рядок містить кількість рядів N (1 N 1000) у стеці. i-тий з наступних N рядків містить i цілих чисел B_ij (-10^5B_ij10^5 для 1 j i N); значення B_ij дорівнює числу, записаному на j-й кулі у i-ому ряду стека (першийй ряд - самий верхній, у кожному ряду першою кулею є сама ліва).

За останнім тестом йде рядок, який містить один нуль.

Вихідні дані

Для кожного теста вивести у окремому рядку ціле число - максимальний приз, який може отримати участник гри для заданого стека куль.

Приклад

Вхідні дані #1
4
3
-5 3
-8 2 -8
3 9 -2 7
2
-2
1 -10
3
1
-5 3
6 -4 1
0
Вихідні дані #1
7
0
6
Джерело ACM ICPC Latin America 2011, November 4th-5th, 2011