Helicopter Delivery Mission

Little Blue is a helicopter pilot responsible for delivering supplies to n mountainous villages each month. Every month, he must fly from the headquarters (located at village 1), visit each village at least once (possibly more than once), and return to headquarters.

Each village has a helipad with a refueling station. The distance between any two villages is the straight-line (Euclidean) distance between their coordinates. However, due to a limited fuel tank, the helicopter cannot fly more than D distance in any single flight. If the direct distance between two villages exceeds D, Little Blue may refuel by stopping at intermediate villages (including the headquarters) along the way, as long as each flight segment does not exceed D in length.

Your task is to determine the minimum total flight distance required to complete the monthly delivery mission.

Formally, you are given an integer n and a floating-point number D. Then, for each village you are given its coordinates. There is an edge between any two villages if and only if their Euclidean distance is at most D. Using these allowed direct flights (or a sequence of them via intermediate stops), compute the shortest possible closed route starting and ending at village 1 that visits every village at least once. If it is impossible to reach all villages under the given constraints, output -1.

inputFormat

The first line contains two numbers n and D, where n (1 ≤ n ≤ 15) is the number of villages and D is the maximum distance the helicopter can fly in a single leg.

Then follow n lines, each containing two space-separated integers x and y, which represent the coordinates of the villages. The villages are numbered from 1 to n, with village 1 being the headquarters.

outputFormat

Output a single number indicating the minimum total flight distance required to complete the mission. If it is impossible to visit all villages under the given constraints, output -1.

sample

4 5
0 0
3 4
6 0
3 -4

16.0000000000