Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BALL11 - Empilhamento de bolas

O canal de TV XYZ está desenvolvendo uma novo game show, onde o competidor tem que fazer algumas escolhas de modo a obter um prêmio. O jogo consiste de uma pilha triangular de bolas, cada uma delas tendo um valor inteiro, como mostrado no exemplo a seguir.

O competidor deve escolher quais bolas ele irá levar e seu prêmio é a soma dos valores destas bolas. Entretanto, o competidor pode levar uma bola apenas se ele também levar todas as bolas diretamente acima dela. Isto pode requerer levar bolas adicionais usando a mesma regra. Note que o competidor pode escolher não levar bola alguma, caso no qual o prêmio é zero.

O diretor do programa de TV está preocupado a respeito do prêmio máximo que um competidor pode obter dada uma pilha. Como ele é seu chefe e ele não sabe como responder essa questão, ele atribuiu esta tarefa a você.

Entrada

Cada caso de teste é descrito usando várias linhas. A primeira linha contém um inteiro N representando o número de linhas da pilha (1 ≤ N ≤ 1000). A i-ésima das próximas N linhas contém i inteiros Bij (-105 ≤ Bij ≤ 105 e 1 ≤ j ≤ i ≤ N); o número Bij é o valor da j-ésima bola na i-ésima linha da pilha (a primeira linha é a mais ao topo, e em cada linha a primeira bola é a mais a esquerda).

O último caso de teste é seguido por uma linha contendo um zero.

Saída

Para cada caso de teste imprima uma linha com um inteiro representando o prêmio máximo que um competidor pode fazer a partir da pilha.

Exemplo

Entrada

4 
3 
-5 3 
-8 2 -8 
3 9 -2 7 
2 
-2 
1 -10 
3 
1 
-5 3 
6 -4 1 
0 

Saída

7
0
6


Adicionado por:Wanderley Guimarăes
Data:2012-05-27
Tempo limite:0.159s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Final Sul-Americana da Maratona de Programaçăo da ACM 2011

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.