O triângulo

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 (Figura 1)

A figura 1 mostra um triângulo.

Escreva um programa que calcula a maior soma de números em uma rota que começa no topo do triângulo e termina na base. Em cada passo você pode ir diretamente para linha de baixo, ou na diagonal da direita para linha baixo.

Formalmente da linha $$i$$ e coluna $$j$$, você pode ir para $$(i+1, j)$$ ou $$(i+1, j+1)$$. O total é a soma de todos os números por qual você passou.

Entrada

A primeira linha contém um inteiro $$n\ (1 \leq n \leq 1000)$$. A $$i$$-ésima das próximas $$n$$ linhas vai conter $$i$$ inteiros entre 1 e 100, os valores do triângulo.

Saída

Imprima a maior soma pelas condições do problema.

Exemplos