Considera el triángulo numérico de abajo. Escribe un programa que calcule la máxima suma de números de una ruta que comienza arriba y termina en algún punto de la base. Cada paso puede ir diagonalmente hacia abajo a la izquierda o a la derecha.

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

En el ejemplo, la ruta 7, 3, 8, 7, 5 produce la suma máxima: 30.

Entrada

La primera línea contiene el número de filas $R$ ($1 \le R \le 1000$). Cada línea posterior contiene los enteros de la fila correspondiente del triángulo. Todos son no negativos y no mayores que 100.

Salida

Una línea contiene la suma máxima con el recorrido indicado.

Ejemplos

Entrada 1

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

Salida 1

30