Pairs#284
Mirko and Slavko are playing with toy animals. First, they choose one of three boards shown in the figure above. Each board consists of cells (shown as circles) arranged into a one-, two-, or three-dimensional grid.
Then, Mirko places animals on these cells.
The distance between two cells is the minimal number of steps required for an animal to move from one cell to the other. In one step, the animal can move to an adjacent cell (adjacent cells are connected by lines in the figure).
Two animals can hear each other if the distance between their cells is at most . Slavko's task is to count the number of pairs of animals that can hear each other.
Write a program that, given the board type, the positions of all animals, and the number , determines the number of pairs of animals that can hear each other.
The first line contains four integers, in this order:
board type (1 \leq B \leq 3)
number of animals (1 \leq N \leq 100\,000)
largest distance at which two animals can hear each other (1 \leq D \leq 100\,000\,000)
size of the board (the largest coordinate appearing in the input):
if B = 1, will be at most
if B = 2, will be at most
if B = 3, will be at most
Each of the next lines contains integers separated by spaces—the coordinates of the animal. Each coordinate is between and inclusive.
More than one animal may occupy the same cell.
Output a single integer: the number of pairs of animals that can hear each other.
Example 1