Considere o triângulo numérico abaixo. Escreva um programa que calcule a maior soma dos números em um caminho que começa no topo e termina em algum ponto da base. Cada passo pode ir diagonalmente para baixo à esquerda ou à direita.

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

No exemplo, o caminho 7, 3, 8, 7, 5 produz a maior soma: 30.

Entrada

A primeira linha contém o número de linhas $R$ ($1 \le R \le 1000$). Cada linha seguinte contém os inteiros da linha correspondente do triângulo. Todos são não negativos e não maiores que 100.

Saída

Uma linha contém a maior soma com o percurso especificado.

Exemplos

Entrada 1

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Saída 1

30