Državno natjecanje iz informatike 2018. / Prva podskupina (1. i 2. razred) - 2. zadatak

Satelitima promatramo \(N\) Sunčevih pjega. Svaka pjega vidi se periodički, svaki dan u istom vremenskom intervalu. Sve intervale izražavamo u istoj (UTC) vremenskoj zoni, pa interval u kojem je vidljiva pojedina pjega može sadržavati i trenutak ponoći, tj. može početi prije \(23\):\(59\):\(59\) i završiti nakon \(00\):\(00\):\(00\).

Snimke naših satelita uvijek su duljine \(D\) sekundi i snimaju sve pjege koje su u intervalu snimanja barem na trenutak vidljive. Na primjer, ako snimka počne u \(23\):\(59\):\(50\) i traje \(72\) sekunde, završit će u \(00\):\(01\):\(02\), te će snimiti sve vidljive pjege u tom intervalu, uključujući i pjegu čija je vidljivost završila u \(23\):\(59\):\(50\), ali i onu čija je vidljivost tek počela u \(00\):\(01\):\(02\).

Želimo napraviti dnevni raspored snimaka iz satelita koji ćemo ponavljati iz dana u dan tako da svaka pjega bude snimljena barem na jednoj snimci svakoga dana, a broj snimaka u danu bude što manji. Napišite program koji računa taj minimalan broj snimaka.

Ulazni​ podaci

U prvom retku nalaze se cijeli brojevi \(N ( 1 \leq N \leq 1000 )\), broj Sunčevih pjega, i \(D ( 0 \leq D\) < \(24\) ⋅ \(60\) ⋅ \(60 )\), duljina snimke satelita u sekundama. Ako je \(D\) = \(0\), snimka je zapravo fotografija.

U svakom od sljedećih \(N\) redaka nalazi se početno i završno vrijeme vidljivosti pjege. Oba su vremena oblika HH:MM:SS \(( 0 \leq\) HH \(\leq 23, 0 \leq\) MM, SS \(\leq 59 )\), pri čemu su brojevi HH, MM i SS zapisani s vodećom nulom ako su jednoznamenkasti. Svaki interval vidljivosti traje manje od \(24\) sata i moguće je da traje samo jedan trenutak (ako su početno i završno vrijeme jednaki).

Izlazni podaci

U jedini redak ispišite traženi minimalan broj snimki.

Bodovanje

U test podatcima ukupno vrijednim \(50 \%\) bodova bit će \(D\) = \(0\).

U test podatcima ukupno vrijednim \(30 \%\) bodova, svaka pjega bit će vidljiva samo u jednom trenutku, tj. početno i završno vrijeme pojedine pjege bit će jednaki.

U test podatcima ukupno vrijednim \(30 \%\) bodova bit će \(N \leq 10\).

U test podatcima ukupno vrijednim \(50 \%\) bodova bit će \(D\) < \(12\) ⋅ \(60\) ⋅ \(60\) i sve pjege bit će vidljive između ponoći i podneva (HH \(\leq 11 )\).

Primjeri test​ podataka

Ulaz

3 72
23:59:59 00:00:00
00:01:02 03:00:00
14:00:00 23:59:50

Izlaz

1

Ulaz

4 0
00:30:59 00:50:59
02:50:00 16:00:00
06:30:00 13:59:59
01:45:00 11:45:00

Izlaz

2

Ulaz

5 3600
06:00:30 06:00:30
03:10:00 03:10:00
04:15:00 04:15:00
15:59:00 15:59:00
03:20:00 03:20:00

Izlaz

4