Rozważ poniższy trójkąt liczbowy. Napisz program obliczający największą sumę liczb na ścieżce zaczynającej się na szczycie i kończącej gdziekolwiek na podstawie. Każdy krok prowadzi ukośnie w dół w lewo lub w prawo.

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

W przykładzie ścieżka przez 7, 3, 8, 7, 5 daje największą sumę: 30.

Wejście

Pierwszy wiersz zawiera liczbę rzędów $R$ ($1 \le R \le 1000$). Każdy następny wiersz zawiera całkowite liczby odpowiedniego rzędu trójkąta. Wszystkie są nieujemne i nie większe niż 100.

Wyjście

Jeden wiersz zawiera największą sumę przy podanym sposobie przejścia.

Przykład

Wejście 1

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

Wyjście 1

30