Betrachte das folgende Zahlendreieck. Schreibe ein Programm, das die größte Summe der Zahlen auf einem Weg von der Spitze zu einer beliebigen Stelle der Grundseite berechnet. Jeder Schritt geht diagonal nach links unten oder rechts unten.

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

Im Beispiel ergibt der Weg über 7, 3, 8, 7, 5 die größte Summe: 30.

Eingabe

Die erste Zeile enthält die Zeilenzahl $R$ ($1 \le R \le 1000$). Jede folgende Zeile enthält die ganzen Zahlen der entsprechenden Dreieckszeile. Alle sind nichtnegativ und höchstens 100.

Ausgabe

Eine Zeile enthält die größte Summe bei der beschriebenen Bewegung.

Beispiele

Eingabe 1

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

Ausgabe 1

30