Стек куль
Телеканал XYZ розробляє нове ігрове шоу, у якому участники повинні зробити деякий вибір щоб отримати приз. Гра складається з трикутного стека куль, на кожній з яких записано цілочисельне значення, як показано нижче на прикладі.
Участник повинен вибрати набір куль, і його призом будет сума чисел на них. Участник може взяти кулю, лише якзо він берет усі кулі, які знаходять безпосередньо над нею. Це может вимагати зняття додаткових куль за описаним правилом. Участник може не брати жодної кулі, у такому випадку його приз буде рівним нулю.
Директор телешоу зацікавлений у тому, щоб участник отримав максимальний приз для заданого стеку. Так як він є Вашим босом, то попросив Вас розв'язати цю задачу.
Вхідні дані
Кожен тест задається у декількох рядках. Перший рядок містить кількість рядів N (1 ≤ N ≤ 1000) у стеці. i-тий з наступних N рядків містить i цілих чисел B_ij (-10^5 ≤ B_ij ≤ 10^5 для 1 ≤ j ≤ i ≤ N); значення B_ij дорівнює числу, записаному на j-й кулі у i-ому ряду стека (першийй ряд - самий верхній, у кожному ряду першою кулею є сама ліва).
За останнім тестом йде рядок, який містить один нуль.
Вихідні дані
Для кожного теста вивести у окремому рядку ціле число - максимальний приз, який може отримати участник гри для заданого стека куль.