Description

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

(Figura 1)

La Figura 1 muestra un triángulo de números. Escriba un programa que calcule la máxima suma de números en una ruta que comience en la cima y termine en cualquier lugar de la base. En cada paso se puede hacia abajo diagonalmente a la izquierda o diagonalmente a la derecha.

Input

Su programa debe leer de la entrada estándar. La primera línea contiene un entero N: el número de filas en el triángulo. Las siguientes N líneas describen los datos del triángulo. El número de filas en el triángulo es > 1 pero <= 100. Los números en el triángulo, todos enteros, están entre 0 y 99.

Output

Su programa debe escribir en la salida estándar. La máxima suma se escribe como un entero.

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

30

Source

Translator

Steinersp