G1 - Miško a kamene

Malý Miško navštevuje svojich starých rodičov veľmi často, ba priam až takmer denne. Keďže ale Miško je veľký huncút, dedo Alojz to s ním má často tažké. Zabaviť Miška na dlhšiu dobu je takmer nemožné, a tak sa dedo snaží vždy vymyslieť niečo nové. Naposledy našiel na povale nejaké staré doskové hry a množstvo bielych a čiernych kameňov. Taktiež sa vopred dobre zásobil cukríkmi, aby Miška motivoval.

Miškovou úlohou je položiť na hraciu plochu čo najväčší počet bielych kameňov. Aby to nemal také jednoduché, Miško môže položiť biely kameň iba na také políčko, ktoré už má na políčku vľavo od seba alebo na políčku nad sebou iný biely kameň. Na začiatku hry dedo Alojz vždy položí jeden biely kameň na každé políčko v hornom riadku, a tiež na hraciu plochu umiestní nejaké náhodné množstvo čiernych kameňov. A pokiaľ sa Miškovi podarí položiť na hraciu plochu maximálny možný počet bielych kameňov, dostane od deda práve toľko cukríkov.

Vstup

Prvý riadok vstupu obsahuje čísla X a Y určujúce rozmery hracej plochy. Druhý riadok obsahuje číslo B určujúce počet čiernych kameňov na hracej ploche (1 ≤ B ≤ X·Y). Každý z nasledujúcich B riadkov obsahuje dve čísla – súradnice jedného čierneho kameňa (políčko v ľavom hornom rohu hracej plochy má súradnice [0,0]). Keďže na všetky políčka horného riadka dedo Alojz na začiatku umiestní biele kamene, môžete predpokladať, že žiadny čierny kameň nebude mať y-ovú súradnicu 0.

Výstup

Vypíšte jediný riadok obsahujúci maximálny počet bielych kameňov, ktoré vieme uložiť na hraciu plochu (vrátane bielych kameňov v prvom riadku, ktoré boli položené už na začiatku).

G1

1 ≤ X, Y ≤ 100

G2

1 ≤ X, Y ≤ 10⁹
1 ≤ B ≤ 100 000

Príklad

Vstup:

7 7
8
4 5
5 3
4 6
3 3
2 3
2 4
6 3
4 3

Výstup:

33

Vysvetlenie:

Hracia plocha na začiatku hry vyzerá nasledovne ('o' reprezentuje biely kameň, '*' čierny):

ooooooo
.......
.......
..*****
..*....
....*..
....*..

Po umiestnení maximálneho možného počtu bielych kameňov bude vyzerať takto:

ooooooo
ooooooo
ooooooo
oo*****
oo*....
oooo*..
oooo*..