2150 - 综合练习-dangerous again

在一个城市有 $n \times m$ 个街区,现在已知有一个恐怖组织在其中的一个街区安放了定时炸弹,其威力为 $t$,即所有到这个街区的直线距离(欧几里得距离)小于等于 $t$ 的街区都会受威胁。已知有 $r$ 个可能的炸弹安放位置,现在这里的警长想知道最坏的情况下会有多少街区受威胁。

输入

第一行四个整数 $n,m,r,t$。

接下来 $r$ 行,每行两个整数 $x_i,y_i$,表示炸弹可能安放的位置。

$1\le n,m \le 10^5$,$1\le r \le 50$,$1 \le t \le 300$,$1\le x_i \le n$,$1 \le y_i \le m$。

输出

一个整数,表示最坏的情况下会有多少街区受威胁。

样例

输入

4 5 3 2
1 2
3 4
4 5

输出

11
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题