Se citeste un triunghi de numere cu n linii (linia i contine i numere, 1 <= i <= n). Pornind din varf, la fiecare pas ne putem deplasa catre unul dintre cele doua numere aflate imediat sub cel curent, pe linia urmatoare. Determinati, folosind Programarea Dinamica, suma maxima ce poate fi obtinuta pe un astfel de drum de la varf pana la baza triunghiului.
- Date de intrare
- Pe prima linie se citeste n. Urmeaza n linii, linia i continand i numere.
- Date de iesire
- Se afiseaza un singur numar: suma maxima.
- Restrictii
- 1 <= n <= 1000, -1000 <= numar <= 1000
Exemple
Exemplul 1
Intrare
4 2 3 4 6 5 7 4 1 8 3
Iesire
21
Exemplul 2
Intrare
1 5
Iesire
5