题目描述

你们国家遇上了僵尸问题。也就是说，国家里有僵尸，而这确实是个麻烦。幸好你在法医动物学与僵尸应急研究所（FIZZES）有份稳定工作，你的任务很简单——给出这个问题有多严重的一个衡量值。

你已经把国家地图用一个 $N$ 行 $M$ 列的网格表示，每个格子里是一个非负整数。

你知道所有僵尸的准确位置，且没有两个僵尸在同一个格子。僵尸所在的格子标记为 $0$。接着，所有与标记为 $0$ 的格子相邻（相邻指的是上下左右及四个斜角，一共最多 $8$ 个邻居）的未标记格子都会被标记为 $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\ (1 \le N \le 10^9; 1 \le M \le 10^9)$，表示网格大小。接下来一行包含整数 $K\ (1 \le K \le 2000)$，表示僵尸格子的数量。接下来 $K$ 行，每行包含两个空格分隔的整数 $r_i\ c_i$，表示第 $i$ 个僵尸的行号和列号（$1 \le r_i \le N; 1 \le c_i \le M$）。保证没有两个僵尸在同一格子：如果 $i \ne j$，那么 $(r_i, c_i) \ne (r_j, c_j)$。最后一行包含整数 $Q\ (0 \le Q \le N + M)$。

在 $25$ 分的 $5$ 分中，$N \le 1000$ 和 $M \le 1000$。

$25$ 分的额外 $5$ 分中，$K \le 50$。

$25$ 分的再额外 $5$ 分中，$N \le 1000$。

输出格式

输出网格中标记为整数 $Q$ 的格子数量。

5 6
2
3 3
2 4
2

15

提示

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

翻译来源：GPT 4.1 mini。