좀비 아포칼립스

나라에 좀비가 나타났다. 그게 바로 문제다. 당신은 법의동물학 및 좀비출현연구소(FIZZES)에 근무하며, 사태가 얼마나 심각한지를 수치로 보고하는 일을 맡았다.

나라 전체를 $N \times M$ 크기의 격자로 옮겨 그렸고, 각 칸에 음이 아닌 정수를 하나씩 적는다. 좀비의 위치는 모두 정확히 알고 있으며, 한 칸에 좀비가 둘 이상 있는 경우는 없다. 숫자는 다음 순서로 적는다.

• 좀비가 있는 칸에 $0$을 적는다.
• 아직 숫자가 적히지 않은 칸 중 $0$이 적힌 칸과 맞닿은 칸에 $1$을 적는다.
• 아직 숫자가 적히지 않은 칸 중 $1$이 적힌 칸과 맞닿은 칸에 $2$를 적는다.
• 모든 칸에 숫자가 적힐 때까지 이 과정을 반복한다.

두 칸이 변이나 꼭짓점을 공유하면 맞닿은 것으로 본다. 그래서 한 칸은 최대 여덟 칸과 맞닿는다. 칸에 적힌 숫자는 연구소가 그 지점의 좀비 확산을 어느 정도로 우려하는지 나타내는 등급이다.

$N = 5$, $M = 6$이고 좀비가 2행 4열과 3행 3열에 있으면 숫자는 다음과 같이 적힌다.

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$개 줄에 $i$번째 좀비가 있는 칸의 행 번호와 열 번호를 나타내는 정수 $r_i$와 $c_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$).

$Q$가 적힌 칸의 개수를 출력한다.