Laiko ribojimas: 1s

Atminties ribojimas: 1024MB

Duomenų failas: pletra.in

Rezultatų failas: pletra.out

Jei norite pateikti savo sprendimą - prisijunkite.

4. Plėtra

Tolimoje galaktikoje egzistuoja cilindro formos planeta. Planetą sudaro trys regionai: viršus, apačia bei šoninis regionas.

Viršutinis bei apatinis regionai yra dideli žemynai, kuriuose įsikūrę du milžiniški miestai. Tuo tarpu šoninis regionas yra sudarytas vien tik iš vandenyno.

Vieną dieną miestų gyventojai nusprendė, jog žemynuose nepakanka vietos ir jie norėtų paversti dalį šoninio regiono į sausumą. Šoninis regionas gali būti pavaizduotas kaip r eilučių bei c stulpelių lentelė - kiekvienas lentelės elementas atvaizduoja šoninio regiono plotą. Eilutės yra sunumeruotos nuo 1 iki r nuo viršaus iki apačios, o stulpeliai yra sunumeruoti nuo 1 iki c iš kairės į dešinę. Du plotai yra gretimi, jei turi bendrą kraštinę. Taipogi, du plotai esantys toje pačioje eilutėje - vienas kairiausiame stulpelyje, kitas dešiniausiame - taip pat yra gretimi.

Iš pradžių visi plotai yra okupuoti vandenyno. Miestų gyventojų planas - paversti kai kuriuos plotus į sausumą pagal jums duotą eiliškumą.

Tačiau šoninis regionas taip pat naudojamas susisiekimui tarp žemynų laivais. Formaliau, neleistina paversti šoninio regiono ploto į sausumą, jei nebeegzistuos seka plotų su šiais parametrais:

  1. Visi sekoje esantys plotai priklauso vandenynui (t.y. nepaversti į sausumą).
  2. Pirmas sekos plotas yra pirmoje lentelės eilutėje.
  3. Paskutinis sekos plotas yra paskutinėje lentelės eilutėje.
  4. Iš eilės einantys sekos plotai yra gretimi.

Taigi, persvarsčius planą buvo nuspręsta, jog paverčiant plotą į sausumą miestai pirmiausia turės patikrinti, ar jie nepažeidžia aukščiau aprašytos sąlygos. Jei pažeidžia, tai plotas nepaverčiamas sausuma ir planas tęsiamas nuo sekančio jums duoto eiliškumo ploto. Kitu atveju, plotas paverčiamas į sausumą.

Jūsų darbas - padaryti šio plano simuliaciją ir išvesti sėkmingai paverstų į sausumą plotų skaičių.

Pradiniai duomenys

Pirmoje eilutėje pateikti trys skaičiai r, c ir n (1\\leqr,c\\leq3000,1\\leqn\\leq300000). Toliau seka n eilučių apibūdinančių tvarką, pagal kurią jūs plotus versite į sausumą. Kiekvienoje eilutėje pateikti du skaičiai r_i bei c_i (1\\leqr_i\\leqr,1\\leqc_i\\leqc), apibūdinantys plotą, esantį eilutėje r_i bei stulpelyje c_i.

Rezultatai

Išveskite vieną skaičių - kiek plotų pavyko sėkmingai paversti į sausumą.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
3 4 9
2 2
3 2
2 3
3 4
3 1
1 3
2 1
1 1
1 4
 
6