[IOI2007] pairs 动物对数

Mirko 和 Slavko 正在玩动物玩具的游戏。 首先，他们要在下图给出的三种玩具模板中选择一种。三种模板分别由一维、二维和三维的网格点（在图中用圆圈表示）组成。  接下来Mirko 把 $N$ 个小动物玩具放到选中的模板的网格点上。 动物玩具可以走一步到达与它相邻的网格点上（在图中相邻的点之间有一条小短线相连）。两个网格点之间的距离定义为**从一个网格点到另一个网格点所需要移动的最小步数**。 如果两个动物之间的距离小于等于$D$，则它们之间可以互相听见。Slavko 的任务是计算在模板上有多少对动物可以互相听得见。 给定模板的类型、所有动物的位置以及数字$D$，写一个程序计算有多少对动物可以互相听得见。

输入的第一行按顺序给出四个整数： - 模板类型 $B (1 \leq B \leq 3)$; - 玩具动物的数目 $N (1 \leq N \leq 100 000)$; - 动物之间可以互相听得见的最大距离$D (1 \leq D \leq 100 000 000)$; - 模板的大小 $M$ ( 即在输入中允许的最大的坐标值): 当 $B=1$ 时, $M$ 最大是 $75 000 000$. 当 $B=2$时, $M$ 最大是 $75 000$. 当 $B=3$时, $M$ 最大是 $75$. 接下来的$N$ 行每行包含$B$ 个整数，整数之间用空格隔开，表示一个动物玩具的坐标。坐标的取值范围是$1$ 到 $M$ ( 包括$M$ )。 每个网格点可以同时包含多个动物玩具。

输出应该包括一个整数，表示可以互相听得见的玩具动物的对数。 注意：使用64 位整数类型计算和输出结果 (在 C/C++ 中用```long long```, 在Pascal 中用```int64``` ) 。

1 6 5 100 
25 
50 
50 
10 
20 
23 

4

2 5 4 10 
5 2 
7 2 
8 4 
6 5 
4 4 

8

3 8 10 20 
10 10 10 
10 10 20 
10 20 10 
10 20 20 
20 10 10 
20 10 20 
20 20 10 
20 20 20 

12

在30分的测试数据中, 动物数目 $N$ 最多是 $1 000$。 如果成功通过了某一种模板（一维、二维或者三维）的全部测试数据，将会得到至少30分。 对于input 1的解释： 假设动物按给出的顺序编号为$1$到$6$。$4$对互相能够听得到的动物分别是: - 1-5 ( 距离是5) - 1-6 ( 距离是2) - 2-3 ( 距离是0) - 5-6 ( 距离是3) 对于input 2 的解释：$8$对动物分别是: - 1-2 ( 距离是2) - 1-4 ( 距离是4) - 1-5 ( 距离是3) - 2-3 ( 距离是3) - 2-4 ( 距离是4) - 3-4 ( 距离是3) - 3-5 ( 距离是4) - 4-5 ( 距离是3)