P16011 [CCO 2016 Day 2] Zombie Apocalypse

Your country has a problem with zombies. That is, it has zombies, which are a problem. Thankfully, you are gainfully employed at the Forensic Institute for Zoology and Zombie Emerging Studies (FIZZES), and your job is simply to give a measure of how bad the problem is. You have mapped out your country on an $N$-by-$M$ array of cells marked with non-negative integers. You have the exact locations of all the zombies, and know that no two zombies are in the same location. The cells containing a zombie are marked with $0$. Next, all the unmarked cells touching a cell (where touching a cell means touching on any side or corner of a cell; so each cell touches up to $8$ other cells) marked with $0$ are marked with $1$. Then, all the unmarked cells touching a cell marked with $1$ are marked with $2$. This process continues until all the cells are marked. These numbers indicate the level of concern your office has about the spread of zombies. A small example is shown below. ```plain 2 2 1 1 1 2 2 1 1 0 1 2 2 1 0 1 1 2 2 1 1 1 2 2 2 2 2 2 2 3 ``` Your boss has given you an integer $Q$, and you must determine the number of cells which are marked with the integer $Q$.

The first line of input will contain two space-separated integers $N$ and $M\ (1 \le N \le 10^9; 1 \le M \le 10^9)$ indicating the size of the grid. The next line will contain the number $K\ (1 \le K \le 2000)$, indicating the number of cells that contain zombies. The next $K$ lines each contain two space separated integers $r_i\ c_i$ indicating the row and column of the ith zombie $(1 \le r_i \le N; 1 \le c_i \le M)$. No two zombies are in the same cell: thus if $i \ne j$ then $(r_i, c_i) \ne (r_j, c_j)$. The last line will contain the integer $Q\ (0 \le Q \le N + M)$. For $5$ of the $25$ marks available, $N \le 1000$ and $M \le 1000$. For an additional $5$ of the $25$ marks available, $K \le 50$. For an additional $5$ of the $25$ marks available, $N \le 1000$.

Output the number of cells in the grid that are marked with the integer $Q$.

The sample input is the example shown above, which has $15$ $2$'s.