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 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 vienīgajā rindā jāizvada viens vesels skaitlis - lielākā iespējamā skaitļu ceļa skaitļu summa.

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