说明

在遥远的「坐标王国」里，大地上散落着 $n$ 个祭坛。这些祭坛是王国与诸神沟通的媒介，每一个祭坛都有自己的名字与位置，而它们的位置总是整齐地记录在平面坐标上，永不重复，依序分别为 $(x_1 , y_1 ), (x_2 , y_2 ), \dots , (x_n , y_n )$。

每逢百年一度的「能量苏醒节」，国王必须召集全国祭司，在大地上进行一场庄严神圣的连线仪式。传说中，当某些祭坛之间以神圣的光束相连，能量就会在它们之间流动，进而唤醒沉睡的巨龙与大地之灵，守护整个王国。然而，仪式并不能随意进行。祭司必须遵循古老的规则：

1. 仪式中必须选出 $k$ 条连线，其中 $k$ 的值介于 $1$ 到 $18$ 之间。
2. 每条连线都必须连接两个不同的祭坛。
3. 任何一个祭坛在整个仪式中至多只能参与一条连线，也就是说，所有连线的端点必须互不重复。
4. 任两条连线不可在平面上交叉或重叠，否则会彼此干扰。

能量的流动并非毫无代价。两个祭坛之间的连线会消耗祭司们的法力，而法力的消耗量与它们的距离成正比，而第 $i$ 个祭坛与第 $j$ 个祭坛，即位置 $(x_i , y_i )$ 与位置 $(x_j , y_j )$，之间的距离的定义是欧几里得距离：

$$\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$$

因此，如果选出的连线过长，对祭司们将会是沉重的负担，如果法力不足，将会导致连线仪式无法完成。反之，如果能找到合适的祭坛，使得总连线距离最短，那么仪式就能以最小的法力消耗完成，并且释放出最大的能量。

作为王国的御用解题大师，你肩负重责大任。国王将祭坛的坐标交给你，并要求你算出最小的总法力消耗。为了方便起见，我们采用连线的总长度来代表祭司们法力的总消耗量。你的答案将直接决定仪式能否顺利完成，甚至影响王国的存亡。

输入格式

$$\begin{aligned} &n \; k \\ &x_1 \; y_1 \\ &x_2 \; y_2 \\ &\vdots \\ &x_n \; y_n \end{aligned}$$

• $n$ 为祭坛数量。
• $k$ 为需要选出的连线数量。
• $x_i,y_i$ 代表第 $i$ 个祭坛的坐标是 $(x_i,y_i)$。

输出格式

$$a$$

• $a$ 代表最小的总法力消耗。相对误差或绝对误差在 $10^{-6}$ 以下均视为正确。也就是说，若正确答案是 $b$，则你的答案只要满足$$\frac{\lvert a - b \rvert}{\max(\lvert a \rvert, \lvert b \rvert, 1)} \leq 10^{-6}$$即会被视为正确。

3 1
0 0
0 3
9 9

3.0000000000

4 2
0 0
1 0
5 5
5 6

2.0000000000

提示

数据限制

• $1 \leq k \leq 18$。
• $2k \leq n \leq 10^5$。
• $0 \leq x_i, y_i \leq 10^9$。
• 所有祭坛坐标均不同。
• 输入的数皆为整数。

评分说明

本题共有七组子任务，条件限制如下所示。 每一组可有一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。

子任务	分数	额外输入限制
1	13	$k = 1$。
2	8	$n \leq 20$，$k \leq 10$。
3	11	$n \leq 3000$，$k \leq 2$。
4	15	$k \leq 2$。
5	26	$n \leq 3000$，$k \leq 15$。
6	17	$k \leq 15$。
7	10	无额外限制。