Communication Between Robots

In the year 21xx, human beings are spreading across the galaxy. Since the end of the last century, thousands of pioneer spaceships have been launched to discover new habitable planets.

The Tripenerse is one of those spaceships, heading toward the Andromeda galaxy. After a long cruise through hyperspace, the crew has found a very promising candidate planet. The next step is to investigate whether the planet is really suitable for new residents.

For that purpose, the ship is carrying several unattended landers. Captain Juclean Dripac decided to drop them onto the planet to collect data. Unfortunately, the robots are old and not very clever, so the operator must program what they do on the planet before landing. Many crew members, including you, were called to make this plan.

The most complicated phase of the mission is gathering and integrating the data that the robots collect independently. The robots must establish all-to-all communication channels to exchange data once during the mission. All the robots activate their channels together at a predetermined moment, and they exchange data with each other once, at that exact moment. This moment can be at the very beginning or the very end of the mission, or any time in between. You choose this moment, and the operator programs the robots accordingly.

The robots communicate over wireless channels, so distance does not limit connectivity. However, the farther two robots are apart, the more power they need for communication. Because the battery capacity is limited, you want to save transmission power as much as possible.

On the bright side, the communication units also have routing functions, so robots can talk indirectly through other robots as relays. Consider a graph where the vertices are robots and the edges are the communication channels established between them. If the graph is connected, all-to-all communication is possible.

Your task is to write a program that computes the minimum total transmission power required for all-to-all communication among the robots. They have only one communication session, at a single moment during the mission, and you can choose that moment in advance. Each robot moves in a straight line at a constant velocity. The transmission power for two robots is proportional to the distance between them, so the cost is exactly the sum of the distances between each pair of robots that establish a channel. You may treat the planet surface as a two-dimensional plane, since it is huge. The time needed to exchange data is negligible.

The input contains no more than $200$ datasets. Each dataset has the following format.

$N$ $T$

$x_1$ $y_1$ $vx_1$ $vy_1$

...

$x_N$ $y_N$ $vx_N$ $vy_N$

The first line of each dataset contains two integers. $N$ is the number of robots ($2 \le N \le 16$), and $T$ is the time limit of the mission ($1 \le T < 1000$). Each of the following $N$ lines describes the motion of one robot. $(x_i, y_i)$ is the initial landing position and $(vx_i, vy_i)$ is the velocity of the $i$-th robot ($|x_i|, |y_i| < 10^6$, $|vx_i|, |vy_i| < 1000$).

The last dataset is followed by a line containing two zeros. This line is not part of any dataset and should not be processed. The sum of all $N$ over all datasets does not exceed $1700$.

For each dataset, print on one line the minimum communication cost required for all-to-all communication. You may print any number of digits after the decimal point. The absolute error must be at most $0.001$.