Problem Description

Xiaolan is a helicopter pilot. He is responsible for delivering supplies to $n$ villages in the mountains.

Each month, he must visit every village at least once. He may visit a village more than once to deliver the required supplies.

Each village has exactly one heliport. The distance between any two villages is exactly the straight-line distance between them.

Because the helicopter’s fuel tank is limited, the distance of a single flight cannot exceed $D$. Each heliport has a gas station where the helicopter can refuel to a full tank.

Every month, Xiaolan starts from the headquarters, finishes delivering supplies to all villages, and then returns to the headquarters. If convenient, he may also pass through the headquarters in the middle to refuel.

The headquarters is located at village number $1$.

Question: To complete one month’s task, what is the minimum total flying distance Xiaolan must fly?

Input Format

The first line contains two integers $n$, $D$, representing the number of villages and the maximum distance of a single flight.

The next $n$ lines describe the positions of the villages. In the $i$-th line, there are two integers $x_i$, $y_i$, representing the coordinates of village $i$. The distance between village $i$ and village $j$ is $\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$.

Output Format

Output one line containing a real number, rounded to exactly $2$ decimal places, representing the answer.

4 6
1 1
4 5
8 5
11 1

28.00

Hint

For all testdata, it is guaranteed that $1\le n\le20$, $1\le x_i,y_i\le10^4$, $1\le D\le10^5$.

Lanqiao Cup 2020 National Contest, Group C, Problem I.

Translated by ChatGPT 5