공 쌓기

KDK 방송국이 새 게임 쇼를 만들었다. 참가자는 몇 번의 선택을 하고, 그 선택에 따라 상품을 받는다.

공들이 삼각형 모양으로 쌓여 있고, 각 공에는 정수 하나가 적혀 있다. 맨 위 행에는 공이 $1$개, 그 아래 행에는 $2$개, 이런 식으로 $i$번째 행에는 공이 $i$개 있다. $i$행 $j$열의 공은 바로 아래 두 공 위에 얹혀 있으며, 그 공 위에 얹혀 있는 것은 $(i-1)$행의 공 (최대 두 개), 즉 $(i-1,\ j-1)$과 $(i-1,\ j)$이다.

참가자는 공을 하나씩 고를 수 있고, 고른 공에 적힌 수의 합이 점수가 된다. 공을 고르면 그 공은 삼각형에서 제거된다. 점수가 높을수록 더 좋은 상품을 받는다. 단, 어떤 공은 그 위에 얹혀 있는 공을 모두 이미 고른 경우에만 고를 수 있다. 맨 위 공 $(1,\ 1)$은 위에 얹힌 공이 없으므로 언제든 먼저 고를 수 있다. 참가자는 매 순간 공을 더 고를지 멈출지 선택할 수 있으며, 공을 하나도 고르지 않으면 점수는 $0$이다.

프로그램 PD 김동규는 참가자가 얻을 수 있는 점수의 최댓값이 궁금하다. 그 최댓값은 얼마일까?

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 공이 쌓인 행의 수 $N$이 주어진다. ($1 \le N \le 1000$) 이어지는 $N$개의 줄 중 $i$번째 줄에는 정수 $B_{i1},\ B_{i2},\ \dots,\ B_{ii}$가 공백으로 구분되어 주어진다. ($-10^5 \le B_{ij} \le 10^5$, $1 \le j \le i \le N$) $B_{ij}$는 $i$행 $j$열의 공에 적힌 정수이다. (첫 행이 가장 위 행이고, 각 행의 첫 번째 공이 가장 왼쪽 공이다.)

입력의 마지막 줄에는 $0$ 하나가 주어지며, 이는 입력의 끝을 뜻한다.

각 테스트 케이스마다 참가자가 얻을 수 있는 점수의 최댓값을 한 줄에 하나씩 출력한다.