BALLLSTA  Ball Stack
The XYZ TV channel is developing a new game show, where a contestant has to make some choices 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 which balls he is going to take and his prize is the sum of the values of those balls. However, the contestant can take any given ball only if he also takes the balls directly on top of it. This may require taking additional balls using the same rule. Notice that the contestant may choose not to take any ball, in which case the prize is zero.
The TV show director is concerned about the maximum prize a contestant can make for a given stack. Since he is your boss and he does not know how to answer this question, he assigned this task to you.
Input:
Each test case is described using several lines. The first line contains an integer N representing the number of rows of the stack ( 1N1000). The ith of the next N lines contains i integers B_{ij} ( 10^{5}B_{ij}10^{5} for 1jiN); the number B_{ij} 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).
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.
Sample input:
4 3 5 3 8 2 8 3 9 2 7 2 2 1 10 3 1 5 3 6 4 1 0
Sample output:
7 0 6
hide comments
Simes:
20200104 15:29:22
Similar to BALLSAG. 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20130518 11:07:57
picture is broken because this site: https://icpcarchive.ecs.baylor.edu/ is now unavailable. please fix this.. 

Ashish Lavania:
20121222 12:53:41
Last edit: 20131210 15:59:46 

:D:
20120805 20:21:23
Remember that you can pick any number of balls, that is apart from the "on top" rule balls. 

Jared Deckard:
20120730 23:28:28
balls 
Added by:  Gareev 
Date:  20120730 
Time limit:  1.071s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  ACM Latin America 2011 