Zombie Apocalypse

Your country has zombies, and that is the problem. You work at the Forensic Institute for Zoology and Zombie Emerging Studies (FIZZES), and your job is to report how bad the situation is.

The country is mapped onto an $N \times M$ grid of cells, and every cell gets one non-negative integer. You know the exact location of every zombie, and no two zombies share a cell. The numbers are written in this order.

• Every cell holding a zombie is marked $0$.
• Every unmarked cell touching a cell marked $0$ is marked $1$.
• Every unmarked cell touching a cell marked $1$ is marked $2$.
• This repeats until every cell carries a number.

Two cells touch when they share a side or a corner, so one cell touches up to eight cells. The number in a cell is the level of concern the institute has about zombie spread at that spot.

For $N = 5$, $M = 6$ with zombies in row 2 column 4 and row 3 column 3, the numbers come out like this.

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 gives you an integer $Q$. Determine how many cells are marked with $Q$.

The first line contains two space-separated integers $N$ and $M$ ($1 \le N \le 10^9$, $1 \le M \le 10^9$), the number of rows and the number of columns of the grid.

The second line contains $K$ ($1 \le K \le 2000$), the number of zombies.

Each of the next $K$ lines contains two space-separated integers $r_i$ and $c_i$ ($1 \le r_i \le N$, $1 \le c_i \le M$), the row and the column of the $i$-th zombie. No two zombies share a cell, so $(r_i, c_i) \ne (r_j, c_j)$ whenever $i \ne j$.

The last line contains the integer $Q$ ($0 \le Q \le N + M$).

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