Ball Stacking#5741
The XYZ TV channel is developing a new game show where a contestant has to make choices to win a prize. The game consists of a triangular stack of balls, each labeled with an integer value, as shown below:
The contestant may select any set of balls; their prize is the sum of the values on the chosen balls. However, a contestant can only take a particular ball if all balls directly above it are also taken. This may require taking additional balls to satisfy this condition. The contestant may also choose to take no balls, in which case the prize is zero.
The show's director wants to know the maximum possible prize for a given stack. Since you are the director's assistant, your task is to answer this question.
Each test case consists of several lines. The first line contains an integer (1 \leq N \leq 1000) — the number of rows in the stack.
The next lines describe the stack. The -th of these lines contains integers B_{i,j} (-10^5 \leq B_{i,j} \leq 10^5, for 1 \leq j \leq i \leq N); B_{i,j} is the value of the -th ball in the -th row of the stack (the first row is at the top, and the first ball in each row is the leftmost one).
The last test case is followed by a line containing a single zero.
For each test case, output a single integer on a separate line indicating the maximum prize a contestant can achieve from the given stack.
Пример 1