- Time limit: 1.00 s
- Memory limit: 512 MB
Tie muodostuu osuudesta, joista jokainen on lumen peitossa. Tien varrella on asukasta, joista kukin toivoo, että tie aurattaisiin joltakin väliltä.
Monenko asukkaan toiveen voit enintään toteuttaa, kun ehdit aurata tiestä vain osuutta? Aurattavan alueen ei tarvitse olla yhtenäinen.
Syöte
Ensimmäisellä rivillä on kolme kokonaislukua , ja . Tien osuudet on numeroitu .
Seuraavat riviä kuvaavat toiveet. Kullakin rivillä on kaksi kokonaislukua ja : asukas toivoo tien osuudet 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 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 ja ja toteuttaa ensimmäisen ja kolmannen toiveen.
Rajat
Kaikissa osatehtävissä pätee: