C: 成長する点 - Growing Point -

問題

粘菌コンピュータというものがある。 ある種の粘菌には「餌を求め、餌と餌の最短距離をつなぐ形に変形する」 という性質がある。 これを利用し、餌を「入力」、形を「出力」とみなして コンピュータとして利用することができる。

今、二次元平面上に1つの粘菌の拠点とN個の餌が存在する。それぞれの餌には1からNまでの異なる番号が与えられ、拠点には番号0が与えられている。 この粘菌はある餌を食べるために、その餌と最も近い拠点の最短距離を結ぶ管状に 成長し、食べた位置に新たに拠点を形成する。 新たに形成した拠点は拠点を形成する直前に食べた餌と同じ番号を持つ。 粘菌は拠点以外の場所から成長することはできない。 以降では、拠点と餌を二次元平面上の点、管状に成長した粘菌を複数の線分として考える。

すべての拠点と線分からなる構造を粘菌網と呼ぶ。 粘菌は1つの餌を食べるために次のような操作を繰り返す。

1. まだ食べていない餌の中で粘菌網に最も近い餌を選ぶ。そのような餌が複数存在する場合は番号が最も小さい餌を選ぶ。
2. 選んだ餌と最も近い拠点を選ぶ。そのような拠点が複数存在する場合は、最も拠点の番号が小さいものから取る。
3. 選んだ拠点と餌を結ぶ線分を引く。以降ではこのとき選んだ餌も拠点として扱う。

この粘菌は生きるために必要な栄養を取るのにM個の餌を食べる必要がある。 粘菌がM個の餌を食べるまでに引いたすべての線分の長さの合計を求めよ。 また、出力する値は0.0001以下の誤差を含んでいても良い。

以下の図では入力例2の粘菌の様子を示している。

入力形式

N M X Y
px_1 py_1
...
px_n py_n

1行目には餌の数N（1 \≤ N \≤ 5,000）、食べる餌の個数M （1 \≤ M \≤ N）、番号0の拠点の座標X, Y（−5,000 \≤ X, Y \≤ 5,000）が整数値で与えられる。続くN行には番号順に餌の座標px_i, py_i（1 \≤ i \≤ N）が整数値で与えられる。（−5,000 \≤ px_i, py_i \≤ 5,000） また、番号が異なる餌は異なる座標に存在し、それぞれの餌と番号0の拠点の座標は異なる。

出力形式

成長した距離の合計を1行で出力せよ。また、出力する値は0.0001以下の誤差を含んでいても良い。

入力例1

2 2 0 0
3 3
4 0

出力例1

7.16227766017

最初は番号1の餌と拠点の距離が $3\sqrt{2}$ と番号2の餌と拠点の距離が4なので 番号2の餌が選ばれる。その後番号1の餌と粘菌網との距離が3になり、番号1の餌が選ばれる。

入力例2

4 4 1 3
3 3
2 1
3 1
1 1

出力例2

6.2360679775

図のように餌1、2、4、3の順に粘菌は餌を食べていく

入力例3

16 15 -4077 763
-2480 2841
-2908 -1096
676 -4080
-4988 -2634
3004 -1360
-2272 1773
-4344 -3631
-355 4426
-3740 3634
-3330 2191
-3423 -2999
-3438 2281
4754 -1500
-3440 -3873
-2089 -3419
1426 2793

出力例3

25349.9626798834