CSES - Nauhoitus
  • 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