Državno natjecanje 2020. / Osnovna škola (7. razred) - 2. zadatak

Vedran je našao beskonačan kolut super tankog šarenog selotejpa. Izrezao je N komada te ih označio brojevima od jedan do N. Zatim je uzeo Marinovu najdražu dasku za serviranje čvaraka koja je široka točno koliko i selotejp, a podijeljena je na K jednakih dijelova.

Vedran je svaki komad selotejpa, počevši od onog s oznakom jedan pa do onog s oznakom N, zalijepio na dasku. Komad s oznakom i bi nalijepio tako da u potpunosti prekrije sve dijelove daske s oznakama između Li i Di, uključujući i te dijelove. Pri tome je komade nekad lijepio na samu dasku, a nekad na i preko već prethodno nalijepljenih komada.

Nakon toga je pohitao do Marina i povikao: „Vidi što sam ti uradio od daske, Marine! Sad više nije tako dosadna kao prije“. Marinu se to nije svidjelo i odlučio je s daske odlijepiti sve komade. Prije odljepljivanja pogledao je dasku i zapitao se:

1. Kolika je najveća debljina sloja zalijepljenih komada, tj. koliko je najviše komada zalijepljenih jedan na drugog?

Napiši program koji će na osnovi zadanih ulaznih podataka ispisati odgovor na postavljeno pitanje.

ULAZNI PODACI

U prvom je retku prirodan broj N (1 ≤ N ≤ 105 ), broj iz teksta zadatka.

U drugom je retku prirodan broj K (1 ≤ K ≤ 105 ), broj iz teksta zadatka.

U sljedećih N redaka nalaze se po dva prirodna broja Li i Di (1 ≤ Li ≤ Di ≤ K), brojevi iz teksta zadatka.

IZLAZNI PODATCI

U prvi redak ispiši prirodan broj, odgovor na pitanje iz zadatka.

PROBNI PRIMJERI

Ulaz

3
10
2 4
7 10
5 8

Izlaz

2

Ulaz

5
98800
1 50000
50000 98756
1 98800
2 31132
657 2435

Izlaz

4

Ulaz

5
10
8 10
2 9
4 7
9 9
8 10

Izlaz

4

Objašnjenje

Opis prvog primjera:

Promotrimo izgled daske tijekom lijepljenja gledajući je odozgo.

Najdeblji sloj je bio na dijelovima daske s oznakama 7 i 8 gdje su dva selotejpa bila jedan na drugom.