Migrated from Lutece 597 KuFeng's Treasure

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

God Kufeng was the ruler of Gensokyo. Because of the excellent ability of Sakuya who can control the time flows, God Kufeng decides to give Sakuya a mountain of the treasure like the following picture.

The treasure by many kinds of precious stones, silver and gold mixture. Sakuya need much silver for making knife, but gold haven’t any practical value. So she proposes to take part of the treasure. God Kufeng is a wise king. He add a rule that if Sakuya want to take a kind of the treasure , she must take all treasure above. For example, if Sakuya want to take the treasure value $9$, she must take the treasure value $3,-5,3,-8,2$. Now Sakuya want to take the treasure with the most value, could you help her? Note that if there no such methods for Sakuya to take a positive value(which means God Kufeng play a trick on she),you just output 0.

Input

There are several test cases.

For each test case, the first line is an integer $N$($1\leq N\leq 1000$)which describes the height of the treasure. The next $N$ line describes the value of the treasure. The last line contain only one zero.

Output

For each test case output a line with an integer representing the treasure of maximum value that Sakuya can take.

Samples

4
3
-5 3
-8 2 -8
3 9 -2 7
0

7

Resources

UESTC Training for Dynamic Programming