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

Entrada

Saída

3 8

8 1 0

2 7 4 4

4 5 2 6 5