题目描述

在遙遠的「座標王國」裡，大地上散落著 $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	無額外限制。