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 ith 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 jth ball in the ith 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.
hide comments
Satyaki Upadhyay:
20141029 09:13:12
Last edit: 20141029 09:22:27 

vishwas:
20130622 03:52:42
Last edit: 20130622 03:54:40 

ZODI91:
20120822 16:03:47
easy one :) 

PANKAJ SAINI:
20120712 03:10:48
hey, what is happening there,


npsabari:
20120628 21:30:11
Any Tricky Case? Got many WA :(


NoszĂˇly Csaba:
20120606 07:23:13
hi,


Mitch Schwartz:
20120211 14:02:46
Yes, I also found the text confusing but managed to guess the meaning. The text uses the term "directly on top of" so I'll use the same term, even though it's a bit misleading. Consider this triangle


Ikhaduri:
20120211 08:41:32
fix the problem description, it's impossible to understand. 

Tornike Mandzulashvili:
20120211 06:59:45
What "on the top" means ? Last edit: 20120211 07:00:03 
Added by:  Paulo Costa 
Date:  20120209 
Time limit:  0.858s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  ICMCUSP 