Caselles segures P50250

Statement

Considereu un tauler d’escacs $n \times m$ , on només hi ha $t$ torres. Quantes caselles segures té? En aquest problema, diem que una casella és segura si no està ocupada ni està amenaçada per cap torre. Per exemple, aquest tauler té tres caselles segures (les tres caselles blanques de la tercera fila començant per dalt):

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $n$ , $m$ i $t$ , seguides de les posicions $(f_i, c_i)$ de les $t$ torres. Suposeu que $n$ i $m$ estan entre 1 i $40000$ , que $t$ està entre 1 i 100, que les $f_i$ estan entre 1 i $n$ , que les $c_i$ estan entre 1 i $m$ , i que no hi ha dues torres a la mateixa posició.

Sortida

Per a cada tauler, escriviu el nombre de caselles segures.

Observació

La vostra solució ha de tenir cost menor que $O(n \cdot m)$ , tant en temps com en espai.

Public test cases

Input

4 6 5  1 2  1 4  2 4  4 4  4 6
1 1 1  1 1
2 3 1  1 1
2 3 3  1 1  2 3  2 1
200 100 4  1 1  200 1  1 100  200 100

Output

Information

Author: Salvador Roura
Language: Catalan
Official solutions: C++ Python
User solutions: C++ Python