- Time limit: 1.00 s
- Memory limit: 128 MB
Osallistut festivaaliin, jossa näytetään elokuvaa. Jokaisesta elokuvasta on tiedossa sen alku- ja loppuaika.
Sinulla on suunnitelmaa, milloin saavut paikalle ja lähdet pois. Tehtäväsi on laskea jokaiselle suunnitelmalle, montako elokuvaa ehdit katsoa enintään.
Elokuva täytyy katsoa kokonaan alusta loppuun ja et voi katsoa monta elokuvaa samaan aikaan. Voit katsoa kaksi elokuvaa niin, että toinen päättyy samalla hetkellä kun toinen alkaa.
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua ja : elokuvien määrä ja suunnitelmien määrä.
Sitten syötteessä on riviä, jotka kuvaavat elokuvat. Jokaisella rivillä on kaksi kokonaislukua ja : elokuva alkaa hetkellä ja päättyy hetkellä .
Lopuksi syötteessä on , riviä, jotka kuvaavat suunnitelmat. Jokaisella rivillä on kaksi kokonaislukua ja : milloin tulet paikalle ja lähdet pois.
Tuloste
Tulosta jokaisesta suunnitelmasta suurin mahdollinen elokuvien määrä.
Rajat
Esimerkki
Syöte:
4 3 2 5 6 10 4 7 9 10 5 9 2 10 7 10
Tuloste:
0 2 1