Coding is the closest thing we have to superpower !

1320 : 综合练习-dangerous again
描述

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

输入

第一行四个整数 n, m, r, t。 
接下来 r 行,每行两个整数 x_{i}, y_{i}, 表示炸弹可能安放的位置。 
1 \leq n , m \leq 10^{5} , 1 \leq r \leq 50 ,1 \leq t \leq 300 ,1 \leq x_{i} \leq n, 1 \leq y_{i} \leq m

输出

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

样例

输入

4 5 3 2
1 2
3 4
4 5

输出

11
语言:
主题: