- Time limit: 1.00 s
- Memory limit: 512 MB
Uolevin uusi digiboksi pystyy nauhoittamaan k:ta eri TV-ohjelmaa yhtä aikaa. Saat tiedot päivän TV-ohjelmien alkamis- ja loppumisajoista. Mikä on suurin määrä ohjelmia jotka Uolevi voi nauhoittaa kokonaan?
Syöte
Ensimmäisellä rivillä on kaksi lukua, n ja k, TV-ohjelmien määrä ja montako eri ohjelmaa Uolevin digiboksi voi nauhoittaa yhtä aikaa. Seuraavalla n:llä rivillä on jokaisella kaksi lukua, x_i ja y_i, ohjelman i alkamis- ja loppumisaika.
Tuloste
Tulosta yksi luku, montako TV-ohjelmaa Uolevi voi nauhoittaa.
Rajat
- 1 \le k \le n \le 10^5
- 0 \le x_i < y_i \le 10^9
Esimerkki
Syöte:
3 1 1 2 2 3 2 3
Tuloste:
2
Syöte:
5 2 1 4 5 9 2 7 3 8 6 10
Tuloste:
3