El archipiélago de Byteland consta de ~n~ islas de forma triangular numeradas del ~1~ al ~N~. Cada isla está ubicada por las coordenadas cartesianas de los picos.

La administración quiere comprar helicópteros para transportar los habitantes entre las islas. Un helicóptero podrá proporcionar una ruta entre dos islas en la distancia mínima obtenida horizontal o verticalmente (paralela a los ejes de coordenadas). Además, debido a la capacidad del tanque, dicha ruta no puede exceder un valor ~k~ - número natural. Los helicópteros cruzan las rutas en ambas direcciones.

La inversión debe cumplir las siguientes condiciones:

1. El número de helicópteros comprados será mínimo.

2. El número de parejas de islas entre las que se puede realizar el transporte utilizando uno o más helicópteros debe ser máximo.

3. La cantidad de la longitud de todas las rutas es mínima.

Tarea

Escriba un programa que, conociendo los valores de ~n~, ~k~ y las coordenadas de las islas se pueda determinar las siguientes tareas:

1. el número mínimo de helicópteros que comprará la administración;

2. Número de parejas de islas no reguladas entre las que se puede realizar el transporte en helicóptero directa o indirectamente.

3. La suma de las distancias recorridas por todos los helicópteros comprados (la distancia recorrida por un helicóptero es la distancia entre las islas entre las cuales se transporta).

Entrada

La entrada contiene en la primera línea un valor ~v~, que puede ser ~1~, ~2~ o ~3~, según la tarea a resolver.

En la segunda línea los números naturales ~n~ y ~k~ separados por un espacio, con el significado de arriba, y en las siguientes ~n~ líneas hay seis números naturales ~x_1~, ~y_1~, ~x_2~, ~y_2~, ~x_3~ e ~y_3~ separados por un espacio que representa las coordenadas de las tres islas en el formato (abscisa, ordenada).

Salida

Si el valor de ~v~ es ~1~, la salida contendrá solo el número mínimo de helicópteros que será comprado por la administración.

Si el valor de ~v~ es ~2~, la salida contendrá en la primera línea solo el número máximo de pares de islas entre los cuales se puede realizar el transporte en helicóptero.

Si el valor de ~v~ es ~3~, la salida contendrá en la primera línea la cantidad mínima de rutas de helicóptero.

Restricciones y aclaraciones.

• ~1 \le n \le 100~;

• ~1 \le k \le 1000~;

• Las coordenadas de los picos de las islas son números naturales ~0 \le x_i, y_i \le 10^6~;

• dos islas cualesquiera no tienen puntos comunes;

• en el requisito ~2~, si es posible llegar desde la isla ~A~ a la isla ~B~, obviamente, también se puede acceder desde ~B~ a ~A~, por lo que el par que consta de ~A~ y ~B~ es solo una vez;

• La distancia entre dos islas también puede ser un número real. En el Requisito ~3~, el resultado se requiere con una aproximación de ~0.001~, es decir, el resultado anotado con R se considera correcto, si el resultado de la comisión ~C~ cumple la condición ~| R-C | < 0.001~.

• Para calcular y mostrar un número real ~x~ con la mayor precisión, recomendamos utilizar el tipo doble y se dará en caso de ser real con 10 dígitos después de la coma.

• Para la correcta resolución del requisito ~1~, se otorga el ~20%~ de la puntuación;

• Para la correcta resolución del requisito ~2~, se otorga el ~40%~ de la puntuación;

• Para la correcta resolución del requisito ~3~, se otorga el ~40%~ de la puntuación.

Ejemplo de Entrada #1

1
6 11
100 20 100 30 105 30
20 20 30 30 20 30
200 20 200 30 205 30
100 40 100 50 105 40
10 40 5 40 10 50
10 20 5 30 10 30

Ejemplo de Salida #1

3

Explicación:

Los datos corresponden a las cifras anteriores:

~v = 1~, por lo que sólo se resuelve el primer requisito.

Parejas de islas con transporte directo en helicóptero: ~(1,4) (2,6), (6,5)~ y obtenemos ~3~ helicópteros.

Ejemplo de Entrada #2

2
6 11
100 20 100 30 105 30
20 20 30 30 20 30
200 20 200 30 205 30
100 40 100 50 105 40
10 40 5 40 10 50
10 20 5 30 10 30

Ejemplo de Salida #2

4

Explicación:

Los datos corresponden a las cifras anteriores: ~v = 2~, por lo que solo se resuelve el segundo requisito.

Parejas de islas con transporte directo en helicóptero: ~(1,4)~, ~(2,6)~, ~(6,5)~ y obtenemos ~3~ helicópteros.

La isla ~3~ permanece aislada, por lo que tenemos dos grupos de islas. El primer grupo contiene las islas ~1~ y ~4~ y la segunda islas ~2~, ~5~, ~6~. El primer grupo incluye el par ~(1,4)~, y el segundo grupo incluye el par de islas ~(2,5)~, ~(2,6)~ y ~(5,6)~. En total ~4~ pares de islas entre las cuales se pueden mover en helicóptero directo o por parada (indirecta).

Ejemplo de Entrada #3

3
6 11
100 20 100 30 105 30
20 20 30 30 20 30
200 20 200 30 205 30
100 40 100 50 105 40
10 40 5 40 10 50
10 20 5 30 10 30

Ejemplo de Salida #3

30

Explicación:

Los datos corresponden a las cifras anteriores: ~v = 3~, por lo que solo se resuelve el tercer requisito.

Parejas de islas con transporte directo en helicóptero: ~(1,4), (2,6), (6,5)~ y obtenemos ~3~ helicópteros.

La isla ~3~ permanece aislada, por lo que tenemos dos grupos de islas. El primer grupo contiene las islas ~1~ y ~4~, y la segunda islas ~2, 5, 6~.

Los helicópteros proporcionan transporte directo entre las islas:

~1~ y ~4~ con una distancia vertical igual a ~10~;

~2~ y ~6~ con una distancia horizontal igual a ~10~;

~5~ y ~6~ con una distancia vertical igual a ~10~;

En total, las líneas navieras tienen una distancia de ~30~.