题目描述

译自 CCO 2016 Day2 T2「Zombie Apocalypse」。

你的国家正面临着僵尸危机。没错，就是那种会造成麻烦的僵尸。幸运的是，你有一份稳定的工作，就职于「动物和僵尸新兴研究法医学研究所」，你的任务就是评估僵尸危机的严重程度。

你把国家的地图划分成了一个 $N$ 行 $M$ 列的网格，每个格子上的数字表示不同的风险等级。

你知道所有僵尸的准确位置，并且保证没有两个僵尸在同一个位置。有僵尸的格子标记为 $0$。接下来，所有和标记为 $0$ 的格子相邻的空格子标记为 $1$（相邻指上下左右和对角线方向）。然后，所有和标记为 $1$ 的格子相邻的空格子标记为 $2$。这个过程一直持续到所有格子都被标记。这些数字代表了你所在机构对僵尸扩散的担忧程度。

下面是一个例子：

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

你的老板给你一个数字 $Q$，你需要计算出地图上有多少个格子被标记为 $Q$。

输入格式

输入的第一行包含两个用空格隔开的整数 $N$ 和 $M$，表示网格的大小。第二行包含一个整数 $K$，表示僵尸的数量。接下来的 $K$ 行，每行包含两个用空格隔开的整数 $r_i,c_i$，表示第 $i$ 个僵尸的行号和列号。保证没有两个僵尸在同一个格子内，即如果 $i \neq j$，则 $(r_i, c_i) \neq (r_j, c_j)$。最后一行包含一个整数 $Q$。

输出格式

输出地图上被标记为 $Q$ 的格子的数量。

5 6
2
3 3
2 4
2

15

样例输入就是上面给出的例子，其中有 $15$ 个 $2$。

数据范围与提示

对于 $20\%$ 的数据，$N,M\leq 1000$；
对于另外 $20\%$ 的数据，$K\leq 50$；
对于另外 $20\%$ 的数据，$N\leq 1000$；
对于 $100\%$ 的数据，$1 \leq N,M \leq 10^9,1 \leq K \leq 2000, 1 \leq r_i \leq N, 1 \leq c_i \leq M, 0 \leq Q \leq N+M$。