Državno natjecanje 2015. / Osnovna škola (6. razred) - 3. zadatak

Na prijelazu preko pruge cestu siječe N željezničkih kolosijeka.

Svakim kolosijekom tijekom dana prođe više vlakova, a svim kolosijecima zajedno prođe ukupno M vlakova.

Svaki vlak ima svoju jedinstvenu oznaku predstavljenu prirodnim brojem između 1 i M.

Vlak s nekom oznakom prolazi jednom dnevno.

Za svaki vlak zna se kada počinje prolazak i koliko vagona ima.

Svi vlakovi kreću se takvom brzinom da svakom vagonu treba točno jedna sekunda za prolaz.

Prijelaz se u nekom trenutku smatra slobodnim ako se tada na njemu ne nalazi ni jedan vlak.

Zadan je raspored vlakova koji vrijedi za svaki dan. Odredi broj sekundi u danu tijekom kojih prijelaz nije slobodan.

Napomena: Neće se dogoditi situacija u kojoj će istim kolosijekom istovremeno prolaziti dva vlaka, no različitim kolosijecima vlakovi mogu istovremeno prolaziti.

Napomena: Primijeti da neki vlak može početi prolaziti jednog dana i završiti idućeg (vidi 3. test primjer).

ULAZNI PODATCI

U prvom retku nalaze se dva prirodna broja: N (1 ≤ N ≤ 10), broj kolosijeka i M (1 ≤ M ≤ 100), ukupni broj vlakova.

U i-tom od idućih N redaka nalazi se opis pojedinog kolosijeka. Prvi broj u retku, Ki (1 ≤ Ki ≤ M) je broj vlakova koji prolazi tim kolosijekom. Nakon njega slijedi Ki brojeva, oznake vlakova koji prolaze tim kolosijekom.

U j-tom od idućih M redaka nalaze se dva podatka koja opisuju vlak s oznakom j: broj vagona i vrijeme u kojem vlak počinje prolazak zadano u obliku HH:MM:SS. Broj vagona pojedinog vlaka strogo je manji od broja sekundi u danu.

IZLAZNI PODATCI

U jedini redak ispiši broj sekundi iz teksta zadatka.

PRIMJERI TEST PODATAKA

Ulaz

1 2
2 1 2
500 05:00:00
200 07:15:00

Izlaz

700

Ulaz

2 4
2 1 4
2 3 2
10 07:10:05
3 10:00:30
9 07:10:09
5 10:00:31

Izlaz

19

Objašnjenje

Opis drugog test primjera: Vlak 1 će zauzeti prijelaz do 07:10:14, a vlak 3 do 07:10:17 uključivo.

To je ukupno od 07:10:05 do 07:10:17 uključivo, dakle 13 sekundi.

Vlak 4 će zauzeti prijelaz do 10:00:35, a vlak 2 do 10:00:32 uključivo. To je ukupno od 10:00:30 do 10:00:35 uključivo, dakle 6 sekundi.

Ukupno, to je 19 sekundi u danu.

Ulaz

2 2
1 1
1 2
150 00:05:00
500 23:58:20

Izlaz

550

Objašnjenje

Opis trećeg test primjera: Vlak 2 će zauzeti prijelaz od 23:58:20 do kraja dana, ali i od 00:00:00 do 00:06:39 uključivo.

Vlak 1 će zauzeti prijelaz od 00:05:00 do 00:07:29. Prijelaz je dakle zauzet od 23:58:20 do kraja dana i od početka dana do 00:07:29. To je ukupno 550 sekundi.