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