Nosaukums
Skaitļu trīsstūris (triangle)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
96%

Definīcija

Skaitļu trīsstūris ir veidots no veseliem nenegatīviem skaitļiem tā, ka tā virsotnē ir viens skaitlis, nākošajā rindā divi skaitļi, ..., pēdējā rindā ir N skaitļi (1<N<=100). Neviena skaitļa vērtība trīsstūrī nepārsniedz 100.

Aplūkosim visus "skaitļu ceļus", kas sākas trīsstūra virsotnē un katrā solī iet vienu līmeni zemāk (uz skaitli, kas atrodas tieši zem šī pa labi vai pa kreisi) līdz nonāk līdz pašai zemākajai rindai.

Uzrakstiet programmu, kas dotajam trīsstūrim nosaka, kāda var būt lielākā skaitļu ceļa skaitļu summa!

Dotajā piemērā šī summa ir 30 (7+3+8+7+5).


Ievaddatu raksturojums

Ievaddatu pirmā rinda satur naturālu skaitli N(1<=N<=100) - trīsstūra skaitļu rindu skaitu.

Tālāk seko N datu rindas, katra no kurām apraksta vienu skaitļu trīsstūra rindu. Faila i+1-ā rinda atbilst trīsstūra i-tajai rindai (skaitot no augšas) un satur i skaitļus tādā pat secībā kā tie doti trīsstūrī. Starp katriem diviem blakus skaitļiem ievaddatos ir viens tukšumsimbols.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada viens vesels skaitlis - lielākā iespējamā skaitļu ceļa skaitļu summa.


Piezīmes

Uzdevums izmantots 6.Vispasaules informātikas olimpiādē Stokholmā(Zviedrija) 1994.gadā.


Paraugdati

Stdin
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Stdout
30

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.