¡Una tormenta eléctrica ha destruido algunos de los cables de la malla eléctrica del Granja! El Granjero Juan tiene un mapa de todos los ~N~ puntos de conexión ~(2 \leq N \leq 1,000)~, los cuales están numerados convenientemente ~1..N~ y ubicados en coordenadas enteras ~x_i~, ~y_i~ ~(-100,000 \leq x_i \leq 100,000; -100,000 \leq y_i \leq 100,000)~.

Algunos ~W~ ~(1 \leq W \leq 10,000)~ cables conectan pares de puntos de conexión ~P_i~ y ~P_j~ ~(1 \leq P_i \leq N; 1 \leq P_j \leq N)~.

El necesita llevar energía del punto 1 al punto ~N~ (lo cual implica que alguna serie de cables pueden ir del punto 1 al punto ~N~, probablemente a través de un conjunto intermedio de puntos).

Dadas las ubicaciones de los ~N~ puntos y una lista de los cables que permanecieron, determine la longitud mínima de cables requeridos para restaurar la conexión eléctrica de tal manera que la electricidad pueda ir del punto 1 al punto ~N~. Ningún cable puede ser mayor que un número real ~M~ ~(0.0 < M \leq 200,000.0)~.

Como ejemplo, abajo en la izquierda está un mapa de los 9 puntos y 3 cables después de la tormenta. Para esta tarea, ~M~ = 2.0. El mejor conjunto de cables a añadir sería conectar los puntos 4 y 6 y también los puntos 6 y 9.

Después de la tormenta           Reconexión óptima

3  . . . 7 9 . . . . .          3  . . . 7 9 . . . . .
                                          /
2  . . 5 6 . . . . . .          2  . . 5 6 . . . . . .
                                        /
1  2-3-4 . 8 . . . . .          1  2-3-4 . 8 . . . . .
   |                               |
0  1 . . . . . . . . .          0  1 . . . . . . . . .

0 1 2 3 4 5 6 7 8 9             0 1 2 3 4 5 6 7 8 9

La longitud total es entonces 1.414213562 + 1.414213562 = 2.828427124 .

Entrada

• Línea ~1:~ Dos enteros separados por espacio: ~N~ y ~W~.
• Línea ~2:~ Un solo número real: ~M~.
• Líneas ~3..N+2:~ Cada línea contiene dos enteros separados por espacios: ~x_i~ y ~y_i~
• Líneas ~N+3..N+2+W:~ Dos enteros separados por espacios: ~Pi~ y ~Pj~.

Ejemplo de Entrada

9 3
2.0
0 0
0 1
1 1
2 1
2 2
3 2
3 3
4 1
4 3
1 2
2 3
3 4

Detalles de la Entrada

Precisamente los mostrado en el diagrama anterior.

Salida

• Línea ~1:~ Un solo entero en una sola línea. Si restaurar la conexión es imposible, dé como salida –1. En otro caso, dé como salida un solo entero que es 1000 veces el costo mínimo total de restaurar la electricidad. No ejecute ningún redondeo; trunque el producto resultante.

Ejemplo de Salida

2828

Detalles de la Salida

Como en el diagrama anterior.