Juan y Juana están jugando con animales de juguete. Primero, eligen una de las tres tablas que se muestran en la siguiente figura. Cada tablero consta de celdas (que se muestran como círculos en la figura) dispuestas en una cuadrícula de una, dos o tres dimensiones.

Juan luego coloca ~N~ pequeños animales de juguete en las celdas.

La distancia entre dos celdas es el número más pequeño de movimientos que un animal necesitaría para alcanzar una celda de la otra. En un movimiento, el animal puede entrar en una de las celdas adyacentes (conectadas por segmentos de línea en la figura).

Dos animales pueden escucharse entre sí si la distancia entre sus celdas es a lo sumo D. La tarea de Slavko es calcular cuántos pares de animales hay de tal manera que un animal pueda escuchar al otro.

Tarea

Escriba un programa que, dado el tipo de tabla, las ubicaciones de todos los animales y el número ~D~, encuentre el número de pares deseado.

Entrada

La primera línea de entrada contiene cuatro enteros en este orden:

• El tipo de placa ~B (1 \le B \le 3);~

• El número de animales ~N (1 \le N \le 100 000);~

• La mayor distancia ~D~ a la que dos animales pueden escucharse entre sí ~(1 \le D \le 100 000 000);~

• El tamaño del tablero ~M~ (la coordenada más grande permitida para aparecer en la entrada):

• Cuando ~B = 1, M~ será como máximo ~75 000 000.~

• Cuando ~B = 2, M~ será como máximo ~75 000.~

• Cuando ~B = 3, M~ será como máximo ~75.~

Cada una de las siguientes ~N~ líneas contiene ~B~ enteros separados por espacios simples, las coordenadas de un animal de juguete.

Cada coordenada estará entre ~1~ y ~M~ (inclusive).

Más de un animal puede ocupar la misma celda.

Salida

La salida debe consistir en un solo número entero, el número de pares de animales que pueden escucharse entre sí.

Nota: utilice un tipo entero de 64 bits para calcular y generar el resultado (long long en C/C++, int64 en Pascal).

Calificación

En casos de prueba con un valor total de 30 puntos, el número de animales ~N~ será como máximo ~1 000~.

Además, para cada uno de los tres tipos de placas, una solución que resuelva correctamente todos los casos de prueba de ese tipo se otorgará al menos 30 puntos.

Ejemplo #1 de Entrada

1 6 5 100
25
50
50
10
20
23

Ejemplo #1 de Salida

4

Ejemplo #2 de Entrada

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

Ejemplo #2 de Salida

8

Ejemplo #3 de Entrada

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

Ejemplo #3 de Salida

12

Aclaración para el ejemplo más a la izquierda. Supongamos que los animales están numerados del 1 al 6 en el orden en que se dan. Los cuatro pares son:

• 1-5 (distancia 5)

• 1-6 (distancia 2)

• 2-3 (distancia 0)

• 5-6 (distancia 3)

Aclaración para el ejemplo medio. Los ocho pares son:

• 1-2 (distancia 2)

• 1-4 (distancia 4)

• 1-5 (distancia 3)

• 2-3 (distancia 3)

• 2-4 (distancia 4)

• 3-4 (distancia 3)

• 3-5 (distancia 4)

• 4-5 (distancia 3)