BALLSAG - Ball Stacking Again

The XYZ TV channel is developing again a new game show, where a contestant has to make a choice in order to get a prize. The game consists of a triangular stack of balls, each of them having an integer value, as the following example shows:

The contestant must choose exactly one ball and his prize is the sum of the value of that ball and the balls directly on top of it. Notice that the prize can be negative!

Your friend is going to participate on the game show, and he wants you to develop a program that can tell the maximum prize possible.

Input

Each test case is described using several lines. The first line contains an integer N representing the number of rows of the stack ( 0 < N < 1001). The i-th of the next N lines contains i integers Bij ( - 1000 <= Bij <= 1000 for 1 <= j <= i <= N); the number Bij is the value of the j-th ball in the i-th row of the stack (the first row is the topmost one, and within each row the first ball if the leftmost one). After each test case there is a blank line.

The last test case is followed by a line containing one zero.

Output

For each test case output a line with an integer representing the maximum prize a contestant can make from the stack.

Example

Input:
2
-2
1 -10

3
1
-5 3
6 -4 1

0

Output: -1
5

Note:
On the first test case, the optimal solution is to take the ball with value 1, making you remove the ball
with value -2, resulting in -1.

On the second test case the best option is to take the ball with value 1 on the bottom row, resulting in
1+3+1 = 5.


Added by:Paulo Costa
Date:2012-02-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ICMC-USP

hide comments
2012-02-10 12:12:14 Robin Lee
Sample input is wrong. Please fix it.
2012-02-10 12:12:14 shivshnkr
wat is meant by "balls directly on top of it"........?????
2012-02-10 12:12:14 Bruno Adami
There is a 0 missing in the sample input!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.