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.