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

Dan je trokut kao u primjeru. Napravite program koji će ispisati najveću moguću sumu brojeva na putu koji kreće iz vrha trokuta i završava negdje na bazi trokuta. Na svakom koraku moguće je ići dijagonalno dolje lijevo ili dolje desno.

Ulazni podatci

U prvom retku nalazi se jedan broj \(n\) (\(1 \leq n \leq 100\)), veličina trokuta.

U sljedećih \(n\) redaka nalaze se brojevi u trokutu. U \(i\)-tom redu nalaziti će se \(i\) brojeva.

Izlazni podatci

Ispišite traženi broj iz zadatka.

Podzadatci

Ulazni primjera 1

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

Izlaz primjera 1

30