CSES - Datatähti 2020 loppu - Auraus
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Tie muodostuu nn osuudesta, joista jokainen on lumen peitossa. Tien varrella on mm asukasta, joista kukin toivoo, että tie aurattaisiin joltakin väliltä.

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

Syöte

Ensimmäisellä rivillä on kolme kokonaislukua nn, mm ja kk. Tien osuudet on numeroitu 1,2,,n1,2,\dots,n.

Seuraavat mm riviä kuvaavat toiveet. Kullakin rivillä on kaksi kokonaislukua ll ja rr: asukas toivoo tien osuudet lrl \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 141 \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 11 ja 33 ja toteuttaa ensimmäisen ja kolmannen toiveen.

Rajat

Kaikissa osatehtävissä pätee:

  • 0kn0 \leq k \leq n
  • 1lrn1 \leq l \leq r \leq n

Osatehtävä 1 (27 pistettä)

  • 1n151 \leq n \leq 15
  • 0m150 \leq m \leq 15

Osatehtävä 2 (41 pistettä)

  • 1n1001 \leq n \leq 100
  • 0m1000 \leq m \leq 100

Osatehtävä 3 (32 pistettä)

  • 1n5001 \leq n \leq 500
  • 0m10000 \leq m \leq 1000