Segments

Vlad really enjoys drawing points on a piece of paper. He has been doing it all day long, but now he decides that he wants to join some of these points using straight lines. There are $N$ such points, numbered from $0$ to $N-1$, and all of them have integer coordinates. Vlad wants to draw exactly $K$ distinct line segments. For each segment, he chooses both endpoints from the points he has already drawn. He also wants to minimize the total length of the segments, which is the sum of the lengths of the $K$ segments.

You will help Vlad find the minimum total length and all the mandatory points. A point is mandatory if it is an endpoint of at least one of the $K$ segments in every choice of segments that reaches the minimum total length. In other words, if you erase a mandatory point, you cannot reach the same minimum length.

The first line has two positive integers $N$ and $K$. The following $N$ lines contain the coordinates of each point. All coordinates are integers. The points are numbered from $0$ to $N-1$.

On the first line, print the minimum total length with an error of at most $10^{-4}$ (the first 4 decimals must be correct). The following lines contain the indices of the mandatory points in ascending order.

• $2 \le N \le 5000$
• $1 \le K \le N(N+1)/2$
• $1 \le K \le 100$
• All coordinates are integers in the range $[-10^9, 10^9]$.
• The coordinates of the points are not necessarily distinct.
• A point may be used as an endpoint for any number of line segments.