Pokemoni

Zona de joacă a celor doi pokemoni, Fire și Water, poate fi reprezentată ca o hartă bidimensională pe care sunt marcate punctele de coordonate $(x, y)$, unde $0 \leq x \leq N$ și $0 \leq y \leq M$. Dintre aceste $(N + 1) \times (M + 1)$ puncte marcate pe hartă, $P$ puncte sunt puncte speciale unde pokemonii se pot ascunde (hidden-points).
Inițial pokemonul Fire se află în punctul de coordonate $(0, 0)$ și dorește să ajungă în punctul de coordonate $(N , M)$. Acesta se poate deplasa la un moment dat din punctul de coordonate $(x, y)$ în unul dintre punctele vecine $(x, y + 1)$ sau $(x + 1, y)$. Pokemonul Water se află inițial în punctul de coordonate $(N , M)$ și dorește să ajungă în punctul de coordonate $(0, 0)$. Acesta se poate deplasa la un moment dat din punctul de coordonate $(x, y)$ în unul dintre punctele vecine $(x, y − 1)$ sau $(x − 1, y)$.
Ca în orice joc, pokemonii au stabilit reguli, după cum urmează:

1. Pokemonul Fire, începe jocul și își alege primul traseul pe care îl parcurge.
2. Pokemonul Water, își alege traseul pe care îl parcurge, după ce Fire parcurge traseul său.
3. Fiecare pokemon parcurge un traseu care vizitează un număr maxim de puncte speciale dintre cele disponibile.
4. Dacă sunt mai multe trasee cu număr maxim de puncte speciale, va fi ales traseul minim lexicografic.
5. Un punct special odată vizitat își va pierde proprietatea de punct special

Cerință

Date fiind $N , M$ și lista punctelor speciale, scrieți un program care să determine numărul de puncte speciale rămase pe hartă la finalul jocului.

Date de intrare

Fişierul de intrare pokemoni.in conţine pe prima linie numerele naturale $N , M$ și $P$ cu semnificația din enunț. Pe următoarele $P$ linii se află punctele speciale, câte un punct pe o linie; un punct special este specificat prin coordonatele sale $x \ y$. Numerele aflate pe aceeași linie a fișierului de intrare sunt separate prin câte un spațiu.

Date de ieșire

Fişierul de ieşire pokemoni.out va conţine o singură linie pe care va fi scris un număr natural ce reprezintă numărul de puncte speciale rămase pe hartă la finalul jocului.

Restricții și precizări

• $2 < N , M \leq 10 \ 000$
• $1 < P \leq 100 \ 000$
• $0 \leq x \leq N , 0 \leq y \leq M$
• Considerăm că un punct $(x_1, y_1)$ este mai mic decât un punct $(x_2, y_2)$ dacă $x_1 < x_2$ sau $x_1 = x_2$ și $y_1 < y_2$.
• Un traseu $(t_1, t_2, . . . t_{lg})$ este mai mic din punct de vedere lexicografic decât un alt traseu $(s_1, s_2, . . . s_{lg})$ dacă există $i \geq 0$, astfel încât $t_j = s_j$ pentru orice $0 \leq j < i$ și $t_i < s_i$.

Exemplu

pokemoni.in

6 8 12
5 5
1 4
3 6
4 4
6 7
4 7
0 7
1 2
5 1
6 6
2 1
3 2

pokemoni.out

2

Explicație

Cele două posibile trasee alese de pokemoni sunt marcate în imaginea alăturată.

Numărul maxim de puncte speciale ce pot vizitate de pokemonul Fire este $6$.
Există mai multe trasee pentru a vizita cele $6$ puncte speciale:

1. $(1, 2)$ – $(1, 4)$ – $(4, 4)$ – $(5, 5)$ – $(6, 6)$ − $(6, 7)$
2. $(1, 2)$ – $(3, 2)$ – $(4, 4)$ – $(5, 5)$ – $(6, 6)$ − $(6, 7)$

Dintre aceste trasee el a ales primul traseu, acesta fiind minim lexicografic.
Cele $6$ puncte speciale vizitate de pokemonul Fire își pierd calitatea de punct special.
Din punctele speciale rămase pokemonul Water poate vizita maximum $4$.
Rămân la final pe hartă $2$ puncte speciale.