题目描述

圣诞老人 Santa 住在一个二维平面的小镇上，镇上住着 $N$ 个小朋友，按 $1 .. N$ 的顺序标号，第 $i$ 个小朋友的家在坐标 $(X_i,Y_i)$ ，圣诞老人的家在坐标 $(S_X, S_Y)$。

圣诞老人想 按 $1$ 到 $N$ 的顺序 给每个小朋友送礼物，但是他一次性只能最多带 $K$ 个礼物。如果礼物不够，Santa 就要返回自己家补充礼物。

请你求出 Santa 离开家并给所有小朋友送完礼物，最后回到自己家的最短路程。

输入格式

第一行输入 $N,K$

第二行输入 Santa 的坐标 $S_X,S_Y$

接下来 $N$ 行描述小朋友的坐标 $X_i,Y_i$。

输出格式

本题有 SPJ，输出的值与答案的差的绝对值不超过 $10 ^ {-6}$ 视为正确。

3 2
1 1
3 1
1 2
3 2

9.236067977499790

2 1
0 1
-1 1
1 1

4.000000000000000

8 3
735867677 193944314
586260100 -192321079
95834122 802780784
418379342 -790013317
-445130206 189801569
-354684803 -49687658
-204491568 -840249197
853829789 470958158
-751917965 762048217

11347715738.116592407226562

提示

• $1\leq\ K\leq\ N\ \leq\ 2\times\ 10^5$
• $-10^9\leq\ S_X,S_Y,X_i,Y_i\ \leq\ 10^9$
• $(S_X,S_Y)\neq\ (X_i,Y_i)$
• $(X_i,Y_i)\neq\ (X_j,Y_j)\ (i\neq\ j)$

Sample Explanation 1

在上图中，红色圆圈代表圣诞老人的房子，带数字的圆圈代表带这些数字的孩子们的房子。

圣诞老人的行动如下

1. 带着两份礼物离开自己的房子。
2. 去孩子 $1$ 家送一份礼物。
3. 回到他家，补充一份礼物。
4. 去孩子 $2$ 家送一份礼物。
5. 去孩子 $3$ 家送一份礼物。
6. 回到他家。

在这种情况下，圣诞老人走过的距离为 $2+2+1+2+\sqrt{5}=7+\sqrt{5}=9.236\dots$ ，是最小值。