#P2074. 危险区域

危险区域

题目背景

一个恐怖组织在一座城市中安放了定时炸弹,其威力巨大,现在这里的警长想知道最坏的情况下会有多少街区受威胁。

题目描述

在一个城市有 N×MN \times M 个街区,每个街区由坐标描述,如图所示:

11 22 33 \cdots MM
11 (1,1)(1,1) (1,2)(1,2) (1,3)(1,3) \cdots (1,M)(1,M)
22 (2,1)(2,1) (2,2)(2,2) (2,3)(2,3) (2,M)(2,M)
33 (3,1)(3,1) (3,2)(3,2) (3,3)(3,3) (3,M)(3,M)
\vdots \ddots
NN (N,1)(N,1) (N,2)(N,2) (N,3)(N,3) \cdots (N,M)(N,M)

现在已知有一个恐怖组织在其中的一个街区安放了定时炸弹,其威力为 tt,即所有到这个街区的直线距离小于等于 tt 的街区都会受威胁,已知有 kk 个可能的炸弹安放位置,现在这里的警长想知道最坏的情况下会有多少街区受威胁。

输入格式

第一行四个正整数 n,m,k,tn,m,k,t

接下来 kk 行每行两个正整数 xi,yix_i,y_i,描述每个可能安放炸弹的街区。

输出格式

一个正整数为在最坏情况下有多少街区会受威胁。

4 5 3 2
1 2
3 4
4 5
11

提示

数据规模与约定

对于20%20\%的数据 k=1k=1

对于 50%50\% 的数据 1n,m10001 \le n,m \le 10001k201 \le k \le 201t1001\le t \le 100

对于 100%100\% 的数据 1n,m1051 \le n,m \le 10^51k501 \le k \le 50t300t \le 300

fixed by @Cppsteve\color{#5EB95E}{\textsf{Cppsteve}}