SP10581 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.

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

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