Joining Capitals

A distant kingdom has N cities, of which K are capitals. King Richard wants to build transmission lines, each connecting two cities. There must be a path, that is, a sequence of transmission lines, between any pair of capitals.

Each transmission line has a cost, which is the Euclidean distance between the cities it connects. The king is stingy, so he wants the transmission lines built so that the total cost (the sum of the line costs) is as small as possible.

Part A of the figure shows an example kingdom with N = 10 cities, of which K = 4 are capitals. The chief engineer presented the king with the solution in part B, which does minimize the total cost. But the king did not like seeing a capital with more than one transmission line. He therefore imposed a new restriction: a capital may be connected to only one other city. After working hard, the chief engineer presented the new solution shown in part C of the figure. He is not sure whether that solution is optimal, and he needs your help.

Given the coordinates of the cities, write a program that computes the minimum possible total cost of building transmission lines so that every pair of capitals is connected by a path and every capital is connected to only one city.

The first line of the input contains two integers, N and K, with 4 ≤ N ≤ 100 and 3 ≤ K < min(10, N), giving the number of cities and the number of capitals. Each of the next N lines contains two integers X and Y, with −1000 ≤ X, Y ≤ 1000, giving the coordinates of one city. The first K cities are the capitals. No two cities have the same coordinates.

Print one line containing a real number with 5 decimal places, the minimum total cost of building the transmission lines under the constraints above.