장난감 동물

상근이와 선영이는 장난감 동물을 가지고 재미있게 놀려고 한다. 먼저, 아래 세 가지 게임판 중 하나를 선택한다. 각 게임판은 여러 개의 칸(그림에는 동그라미)으로 이루어져 있고, 각 게임판은 일차원, 이차원, 삼차원 모양이다.

상근이는 N개의 작은 장난감 동물을 칸에 넣는다.

두 칸의 거리는 장난감 동물이 한 칸에서 출발해서 다른 칸으로 도착하는데 필요한 이동의 횟수이다. 장난감 동물은 자신이 있는 칸과 인접한 칸 중 하나로 이동할 수 있다. (각 칸과 인접한 칸은 그림에서 선분으로 이어져 있다)

두 장난감 동물이 서로의 소리를 들으려면 두 칸의 거리가 D보다 작거나 같아야 한다. 게임판의 종류와 각 장난감 동물의 위치, 그리고 D가 주어졌을 때, 서로의 소리를 들을 수 있는 장난감 동물의 쌍의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 네 정수 B, N, D, M이 주어진다.

B는 게임판의 종류이다. (1 ≤ B ≤ 3) 문제 설명의 왼쪽 그림이 1번 게임판, 중간 그림이 2번, 오른쪽 그림이 3번 게임판이다.

N은 장난감 동물의 수이다. (1 ≤ N ≤ 100,000)

D는 두 장난감 동물이 서로의 소리를 들을 수 있는 가장 먼 거리이다. (1 ≤ D ≤ 100,000,000)

M은 게임판의 크기이다. (입력으로 들어올 수 있는 가장 큰 좌표값) B가 1인 경우 M은 최대 75,000,000이고, 2인 경우에는 75,000, 3인 경우에는 75이다.

다음 N개의 줄에는 각 장난감 동물의 좌표가 주어진다. 모든 좌표는 1보다 크거나 같고, M보다 작거나 같은 자연수이다.

같은 칸에 장난감 동물 여러 개가 들어가 있을 수도 있다.

첫째 줄에 서로의 소리를 들을 수 있는 장난감 동물의 쌍의 수를 출력한다.

1-2 (거리 2) 
1-4 (거리 4) 
1-5 (거리 3) 
2-3 (거리 3) 
2-4 (거리 4) 
3-4 (거리 3) 
3-5 (거리 4) 
4-5 (거리 3)