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$