Installing Power Plant Cables

A severe lightning strike broke many cables, so the power supply is currently down. The first task is to reconnect power plant 1 and power plant N.

The power plants are numbered from 1 to N and are located on a two-dimensional grid. Some cables still remain and connect certain pairs of plants. Given the remaining cables and the locations of all plants, connect plant 1 to plant N while minimizing the total length of newly installed cables. The connection path may pass through other power plants. For safety, the length of a cable directly connecting two plants cannot exceed M. The diagram below shows one possible connection.

         before connection                 after connection

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

The first line contains the number of power plants N(1 <= N <= 1,000) and the number of remaining cables W(1 <= W <= 10,000). The second line contains the maximum cable length M(0.0 < M < 200,000.0).

Each of the next N lines contains the X-coordinate and Y-coordinate xi, yi(-100,000 <= xi, yi <= 100,000) of one power plant, in order from plant 1 to plant N. Each of the following W lines contains two integers, the numbers of the two power plants connected by one remaining cable.

Print the minimum total length of additional cable needed to connect plant 1 and plant N, multiplied by 1000, with all digits after the decimal point discarded.