Državno natjecanje 2020. / Osnovna škola (5. razred) - 3. 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 ili 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 zalijepljeno jedan na drugog?

Marin je odljepljivao komade na način da bi prvo odredio koji je slobodan i onda bi ga odlijepio. Komad je slobodan ako na sebi, ni na jednom svom dijelu, nema zalijepljen drugi komad. Ako istovremeno ima više slobodnih komada, odabrat će onog koji ima najmanju oznaku. Marin je nakon odrađenog posla posložio čvarke na oslobođenu dasku i zapitao sam sebe još jedno pitanje:

1. Koji komad sam prvi odlijepio, tj. koja je bila oznaka tog komada?

Napiši program koji će na osnovi zadanih ulaznih podataka ispisati odgovore na postavljena pitanja.

ULAZNI PODACI

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

U drugom je retku prirodan broj K (1 ≤ K ≤ 30), 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 prvo pitanje iz teksta zadatka.

U drugi redak ispiši prirodan broj, odgovor na drugo pitanje iz teksta zadatka.

PROBNI PRIMJERI

Ulaz

3
10
2 4
7 10
5 8

Izlaz

2
1

Ulaz

2
10
1 5
5 10

Izlaz

2
2

Ulaz

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

Izlaz

4
3

Objašnjenje

Opis prvog primjera: Promotrimo izgled daske tijekom lijepljenja i odljepljivanja gledajući je odozgo.

Najdeblji sloj je bio na dijelovima daske s oznakama 7 i 8 gdje su dva selotejpa bila jedan na drugom. Marin je prvo odlijepio komad s oznakom „1“ (mogao je i komad „3“, ali je gledao manju oznaku).