MRAVOGRA  Mravograd
The hard working ants have built a town called Ant Town. They modeled their town after Manhattan, with H horizontal and V vertical streets which cross in V×O intersections. As ants don't like water, with the first raindrops comes chaos in Ant Town. Town authorities have placed umbrellas under which any number of ants can hide, but only on N intersections.
When the rain starts, each ant on an intersection starts running, using streets, to the nearest intersection with an umbrella. But, if an ant can choose from more than one such intersection, it panics and, not knowing where to go, stays on its starting intersection and gets wet. Town authorities use the name "wet intersections" for such starting intersections.
For example, if Ant Town has 10 horizontal and 10 vertical streets, and if there are 4 intersections with umbrellas, then the question marks in the figure represent "wet intersections":
Picture represents first example. We count streets from left to right from 1 to V and from down upwards from 1 to H.
Write a program which, given the locations of intersections with umbrellas, determines the number of "wet intersections" in Ant Town.
Input
The first line contains two integers H and V (1 ≤ H, V ≤ 30 000), the numbers of horizontal and vertical streets in Ant Town.
Horizontal streets are numbered 1 to H, vertical streets 1 to V.
The second line contains an integer N (1 ≤ N ≤ 10), the number of intersections with umbrellas.
Each of the following N lines contains two integer h and v, meaning that there is an umbrella on the crossing of horizontal street h and vertical street v. The locations of all umbrellas will be distinct.
Output
Output the number of "wet intersections" in Ant Town.
Example
Input:
10 10
4
4 4
4 6
6 4
9 9
Output:
19
Input:
9 9
3
2 2
5 5
8 8
Output:
36
Input:
100 100
2
50 50
50 51
Output:
0
hide comments
linkret:
20160322 21:52:52
Wonder what the 0.00 solution is... 

:D:
20110509 05:32:48
Test cases are correct. You can check them using trivial O(H*V*N) brute force algo. Use the same approach to generate your own test cases.


V0iD!:
20110506 07:19:03
is the output for 2nd test case correct? shouldn't it be 34?

Added by:  Stjepan Glavina 
Date:  20110505 
Time limit:  0.189s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Croatian National 2007 