Županijsko natjecanje 2016. / Osnovna škola (8. razred) - 2. zadatak

Pri ulasku u jednu daleku državu prtljagu će vam pregledati tri carinika, svaki u svojoj kućici.

U kućici A, carinik će vam pregledati ručnu prtljagu.

Kada pregled završi, idete dalje u kućicu B gdje će vam drugi carinik pregledati kofer.

Kada i taj pregled završi, idete dalje u kućicu C gdje treći carinik na temelju procjena prvih dvaju carinika određuje koliko morate platiti carinu.

Za prolazak kroz carinu čeka N ljudi i za svakog smo procijenili koliko će vremena provesti u kojoj kućici.

Vrijeme prelaska iz jedne u drugu kućicu je zanemarivo (ako nema čekanja), ali može se stvoriti gužva ispred bilo koje kućice jer nitko ne može u nju ući dok prethodna osoba u redu ne završi s pregledom.

Kroz svaku kućicu se mora proći pa i onda kada je vrijeme čekanja procijenjeno na nula sekundi.

Tvoj je zadatak, znajući koliko će svaki od N ljudi provesti kod svakog carinika, odrediti ukupno vrijeme potrebno da svi prođu carinu (tj. da posljednji čovjek izađe iz posljednje kućice).

Primjer. U prvom test primjeru niže, na prolazak kroz carinu čekaju tri osobe, a treću kućicu možemo zanemariti jer će svi u njoj provesti 0 minuta.

Prolazak teče ovako:

• Prvi u redu je Mateo koji će provesti 2 minute u kućici A i odmah potom 4 minute u kućici B.
• Iza njega je Sandra, koja očito mora čekati 2 minute da uđe u kućicu A. Ona potom u kućici A provodi svoju 1 minutu, nakon čega ne može odmah ući u kućicu B, nego mora čekati još 3 minute da Mateo izađe iz kućice B i tek tada u njoj provesti svojih 7 minuta, nakon čega iz nje izlazi (ukupno 13 minuta od početka).
• Treći u redu je Robert koji će ući u kućicu A čim Sandra iz nje izađe (3 minute od početka). Nakon što provede svoju 1 minutu u kućici A, morat će (sa Sandrom) čekati ispred kućice B dok iz nje ne izađe najprije Mateo, a potom i Sandra (13 minuta od početka). Konačno, Robert izlazi iz kućice B nakon što u njoj provede 7 minuta (što je ukupno 20 minuta od početka).

ULAZNI PODATCI

U prvom retku nalazi se prirodan broj N (1 ≤ N ≤ 10), broj ljudi u redu.

U svakom od sljedećih N redaka nalaze se po tri cijela broja a, b i c (0 ≤ a, b, c ≤ 15), vrijeme provedeno u kućicama A, B i C (redom), po redcima za osobe od prve do posljednje u redu.

IZLAZNI PODATCI

U jedini redak ispiši traženo ukupno vrijeme.

PRIMJERI TEST PODATAKA

Ulaz

3
2 4 0
1 7 0
1 7 0

Izlaz

20

Opis

Opis prvog test primjera: vidi tekst zadatka.

Ulaz

3
2 4 7
1 7 5
1 7 3

Izlaz

23

Objašnjenje

Opis drugog test primjera:

prolazak kroz kućice A i B odvija se kao u prvom primjeru.

Nadalje, iz kućice C prva osoba izlazi 13 minuta od početka, nakon čega u nju odmah ulazi druga osoba (koja je u tom trenutku izašla iz kućice B).

Nakon još 5 minuta, kućica C je slobodna, ali treća osoba u nju ulazi tek nakon što prođe kućicu B (20 minuta od početka) i završava s pregledom nakon još 3 minute.