Problem E
Forest Fire
Languages
en
ja
sv
A fire has broken out in the integer forest! The integer forest consists of an infite twodimensional plane where there is a tree at each point with integer coordinates. Currently, $N$ of these trees are on fire. Each minute, the fire spreads from every burning tree to its four neighbours (the trees immediately north, east, west and south). To stop the fire, the fire marshals have chopped down $M$ trees. A choppeddown tree can not catch fire, so these points act like a kind of wall to the flames. You are interested in the damage that the fire will cause. In $T$ minutes, there will be a great rain storm that will put out the entire fire. Therefore, you want to know how many trees are on fire after $T$ minutes.
Input
The first line contains three integers:

the number of burning trees $N$ ($1 \leq N \leq 100$),

the number of choppeddown trees $M$ ($0 \leq M \leq 100$),

and the number of minutes to the great rain storm $T$ ($0 \leq T \leq 10^9$).
The following $N$ lines contains two integers $x_ i,y_ i$ ($0 \leq x_ i, y_ i < 10^5$), the coordinates of the burning trees.
The following $M$ lines contains two integers $x_ i,y_ i$ ($0 \leq x_ i, y_ i < 10^5$), the coordinates of the choppeddown trees.
No two trees, either burning or chopped down, will have the same coordinates.
Output
Output a single integer, the number of trees that are on fire after $T$ minutes.
Scoring
Your solution will be tested on a set of test case groups. To get the points for a group, you need to pass all the test cases in the group.
Group 
Points 
Constraints 
$1$ 
$5$ 
$N = 1$, $M = 0$ 
$2$ 
$9$ 
$T \leq 100$, $M = 0$, $x_ i, y_ i < 100$ 
$3$ 
$10$ 
$T \leq 400$, $x_ i, y_ i < 100$ 
$4$ 
$11$ 
$M = 0$, $x_ i, y_ i < 100$ 
$5$ 
$21$ 
$x_ i, y_ i < 100$ 
$6$ 
$15$ 
$M = 0$ 
$7$ 
$29$ 
No further constraints 
Explanations of samples
In sample $1$ the fire spreads to $(0,2)$, $(1,3)$ and $(2,2)$. In total, there will be $4$ burning trees.
In sample $2$ the only burning tree is surrounded by choppeddown trees. There is thus only a single burning tree, despite $T$ being large.
In sample $3$ the fire does not have time to spread since $T = 0$, so the answer is $4$.
Sample Input 1  Sample Output 1 

1 1 1 1 2 1 1 
4 
Sample Input 2  Sample Output 2 

1 4 12345678 2 2 1 2 2 1 2 3 3 2 
1 
Sample Input 3  Sample Output 3 

4 1 0 1 1 1 2 2 3 3 4 7 7 
4 
Sample Input 4  Sample Output 4 

1 2 100000 0 0 2 1 1 2 
20000199999 