Considera il triangolo numerico qui sotto. Scrivi un programma che calcoli la massima somma dei numeri su un percorso che parte dalla cima e termina in un punto qualsiasi della base. Ogni passo può andare diagonalmente in basso a sinistra o a destra.

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

Nell'esempio, il percorso 7, 3, 8, 7, 5 produce la somma massima: 30.

Input

La prima riga contiene il numero di righe $R$ ($1 \le R \le 1000$). Ogni riga successiva contiene gli interi della corrispondente riga del triangolo. Sono tutti non negativi e non maggiori di 100.

Output

Una riga contiene la massima somma con il percorso specificato.

Esempi

Input 1

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

Output 1

30