Stacking Balls

KDK Broadcasting has created a new game show. A contestant makes a series of choices, and the prize depends on those choices.

Balls are stacked in the shape of a triangle, and each ball has a single integer written on it. The top row holds $1$ ball, the next row holds $2$, and so on, so row $i$ holds $i$ balls. The ball in row $i$, column $j$ rests on the two balls directly beneath it, and the balls resting directly on top of it are the (at most two) balls of row $i-1$, namely $(i-1,\ j-1)$ and $(i-1,\ j)$.

The contestant may pick balls one at a time, and the score is the sum of the numbers on the picked balls. Picking a ball removes it from the triangle. A higher score wins a better prize. However, a ball may be picked only once every ball resting on top of it has already been picked. The topmost ball $(1,\ 1)$ has nothing on top of it, so it can always be picked first. At any moment the contestant may choose to keep picking or to stop; if no ball is picked at all, the score is $0$.

Program director Dong-gyu Kim wants to know the maximum score a contestant can obtain. What is that maximum?

The input consists of several test cases. The first line of each test case contains $N$, the number of rows the balls are stacked in ($1 \le N \le 1000$). Each of the following $N$ lines describes one row: line $i$ contains the integers $B_{i1},\ B_{i2},\ \dots,\ B_{ii}$ separated by spaces ($-10^5 \le B_{ij} \le 10^5$, $1 \le j \le i \le N$), where $B_{ij}$ is the integer written on the ball in row $i$, column $j$. (The first row is the topmost row, and the first ball of each row is the leftmost ball.)

The last line of the input contains a single $0$, marking the end of the input.

For each test case, print on its own line the maximum score the contestant can obtain.