산불

정수 숲에 산불이 발생했다! 정수 숲은 무한히 넓은 이차원 평면으로 이루어져 있으며, 정수 좌표를 갖는 모든 점에 나무가 한 그루씩 있다. 현재 이 나무들 중 $N$그루가 불타고 있다. 매분 불은 불타는 각 나무에서 인접한 네 나무(바로 북쪽, 동쪽, 서쪽, 남쪽에 있는 나무)로 번진다. 불길의 확산을 막기 위해 소방대는 나무 $M$그루를 베어 냈다. 베어 낸 나무에는 불이 붙을 수 없으므로, 이 지점들은 일종의 벽 역할을 한다. 당신은 화재가 얼마나 큰 피해를 일으킬지 계산하려 한다. $T$분 후에는 큰비가 내려 불을 모두 끌 것이다. 따라서 $T$분 후에 몇 그루의 나무가 불타고 있는지 알고자 한다.

채점

당신의 풀이는 여러 테스트 케이스 그룹에 대해 테스트된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$5$| $N = 1$, $M = 0$

$2$ |$9$| $T \leq 100$, $M = 0$, $x_i, y_i < 100$

$3$ |$10$| $T \leq 400$, $x_i, y_i < 100$

$4$ |$11$| $M = 0$, $x_i, y_i < 100$

$5$ |$21$| $x_i, y_i < 100$

$6$ |$15$| $M = 0$

$7$ |$29$| 추가 제한 없음

첫 번째 줄에는 세 정수가 주어진다.

• 불타는 나무의 수 $N$ ($1 \leq N \leq 100$),

• 베어 낸 나무의 수 $M$ ($0 \leq M \leq 100$),

• 그리고 큰비가 내리기까지 남은 시간(분) $T$ ($0 \leq T \leq 10^9$).

다음 $N$개의 줄에는 불타는 나무의 좌표를 나타내는 두 정수 $x_i,y_i$ ($0 \leq x_i, y_i < 10^5$)가 주어진다.

다음 $M$개의 줄에는 베어 낸 나무의 좌표를 나타내는 두 정수 $x_i,y_i$ ($0 \leq x_i, y_i < 10^5$)가 주어진다.

불타는 나무인지 베어 낸 나무인지와 관계없이, 같은 좌표에 있는 두 나무는 없다.

$T$분 후에 불타고 있는 나무의 수를 나타내는 정수 하나를 출력한다.

예제 $1$에서는 불이 $(0,2)$, $(1,3)$, $(2,2)$로 번진다. 따라서 불타는 나무는 모두 $4$그루이다.

예제 $2$에서는 유일하게 불타는 나무가 베어 낸 나무들에 둘러싸여 있다. 따라서 $T$이 매우 크더라도 불타는 나무는 한 그루뿐이다.

예제 $3$에서는 $T = 0$이므로 불이 번질 시간이 없으며, 따라서 답은 $4$이다.