- Time limit: 1.00 s
- Memory limit: 512 MB
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$
- $1 \leq n \leq 15$
- $0 \leq m \leq 15$
- $1 \leq n \leq 100$
- $0 \leq m \leq 100$
- $1 \leq n \leq 500$
- $0 \leq m \leq 1000$