Considérez le triangle de nombres ci-dessous. Écrivez un programme calculant la somme maximale des nombres rencontrés sur un chemin partant du sommet et aboutissant quelque part sur la base. Chaque pas descend en diagonale à gauche ou à droite.

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

Dans l'exemple, le chemin 7, 3, 8, 7, 5 produit la somme maximale : 30.

Entrée

La première ligne contient le nombre de rangées $R$ ($1 \le R \le 1000$). Chaque ligne suivante contient les entiers de la rangée correspondante du triangle. Tous sont non négatifs et au plus 100.

Sortie

Une ligne contient la somme maximale obtenue avec le parcours indiqué.

Exemples

Entrée 1

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

Sortie 1

30