Một cơn bão đã phá hủy một số đường dây điện của nông trang! Nông dân John có một bản đồ tất cả \(N\) \((2 \le N \le 1000)\) cây cột điện, để thuận tiện ta đánh số các cột này từ \(1 \rightarrow N\), mỗi cột này được xác định trên mặt phẳng bởi \(2\) số nguyên \(x_i, y_i\) \((-10^5 \le x_i, y_i \le 10^5)\)

Hiện có \(W\) \((1 \le W \le 10^4)\) đường dây điện nối các cặp cột điện \(i\) và \(j\) \((1 \le i, j \le N)\). John cần mang điện từ cột \(1\) đến cột \(N\) (thông qua các đường dây điện và các cột điện khác).

Cho tọa độ của \(N\) cột điện và danh sách những đường dây điện vẫn còn hoạt động. Hãy xác định độ dài nhỏ nhất của các đường dây điện cần thêm để sao cho điện từ cột \(1\) có thể truyền tới cột \(N\). Biết rằng độ dài tối đa của \(1\) đường dây điện là \(1\) số thực \(M\) \((0 \le M \le 2 \times 10^5)\)

Ví dụ, dưới đây là bên trái là bản đồ \(9\) cột điện và \(3\) dây nối vẫn còn hoạt động sau cơn bão. Trong ví dụ này, \(M=2.0\) Cách tốt nhất là ta thêm \(2\) đường dây điện nối \(4-6\) và \(6-9\)

      Sau cơn bão                   Phương án tối ưu

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

Tổng độ dài là \(1.414213562 + 1.414213562 = 2.828427124\)

Dữ liệu vào

• Dòng 1: Hai số nguyên cách nhau bởi dấu cách: \(N\) và \(W\)
• Dòng \(2\): Một số thực \(M\)
• Dòng \(3..N+2\): Mỗi dòng gồm \(2\) số nguyên cách nhau bởi dấu cách: \(x_i\) và \(y_i\)
• Dòng \(N+3...N+2+W\): \(2\) số nguyên cách nhau bởi dấu cách: cột \(i\) và cột \(j\)

Dữ liệu ra

• Dòng \(1\): Một số nguyên trên \(1\) dòng. Nếu không có phương án để cấp điện cho cột \(N\) từ cột \(1\) thì ghi ra \(-1\). Nguojc lại, ghi \(1\) số nguyên là tổng độ dài nhỏ nhất nhân với \(1000\).
• Chú ý không làm tròn, làm giảm tích thu được ở trên.

Input 1

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

Output 1

2828