CSES - Datatähti 2020 loppu - Auraus
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Tie muodostuu $n$ osuudesta, joista jokainen on lumen peitossa. Tien varrella on $m$ asukasta, joista kukin toivoo, että tie aurattaisiin joltakin väliltä.

Monenko asukkaan toiveen voit enintään toteuttaa, kun ehdit aurata tiestä vain $k$ osuutta? Aurattavan alueen ei tarvitse olla yhtenäinen.

Syöte

Ensimmäisellä rivillä on kolme kokonaislukua $n$, $m$ ja $k$. Tien osuudet on numeroitu $1,2,\dots,n$.

Seuraavat $m$ riviä kuvaavat toiveet. Kullakin rivillä on kaksi kokonaislukua $l$ ja $r$: asukas toivoo tien osuudet $l \dots r$ aurattaviksi.

Tuloste

Tulosta yksi kokonaisluku: montako toivetta voit enintään toteuttaa.

Esimerkki 1

Syöte:
6 4 4
1 3
3 4
2 3
3 6


Tuloste:
3

Selitys: Voit aurata osuudet $1 \dots 4$ ja toteuttaa kolme ensimmäistä toivetta.

Esimerkki 2

Syöte:
3 3 2
1 1
1 3
3 3


Tuloste:
2

Selitys: Voit aurata osuudet $1$ ja $3$ ja toteuttaa ensimmäisen ja kolmannen toiveen.

Rajat

Kaikissa osatehtävissä pätee:
  • $0 \leq k \leq n$
  • $1 \leq l \leq r \leq n$
Osatehtävä 1 (27 pistettä)
  • $1 \leq n \leq 15$
  • $0 \leq m \leq 15$
Osatehtävä 2 (41 pistettä)
  • $1 \leq n \leq 100$
  • $0 \leq m \leq 100$
Osatehtävä 3 (32 pistettä)
  • $1 \leq n \leq 500$
  • $0 \leq m \leq 1000$