题目描述

有一个以$xy$平面表示的小镇，圣诞老人和编号为$1$到$N$的$N$个孩子都居住在这里。圣诞老人的家位于坐标$(S_X,S_Y)$处，第$i$个孩子（$1\leq i\leq N$）的家位于$(X_i,Y_i)$处。

圣诞老人需要按照编号顺序给每个孩子各送一份礼物。要给第$i$个孩子送礼物，圣诞老人必须在手中至少持有一份礼物的情况下到访第$i$个孩子的家。不过，圣诞老人每次最多只能携带$K$份礼物，且必须返回自己的家补充礼物（圣诞老人家中有足够多的礼物）。

请你求出圣诞老人从家中出发，给所有$N$个孩子送完礼物后回到家中所需行走的最小距离。

题目约束

• $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)$
• 当$i\neq j$时，$(X_i,Y_i)\neq (X_j,Y_j)$
• 所有输入值均为整数

输入格式

输入数据从标准输入按以下格式给出：

$N$ $K$

$S_X$ $S_Y$

$X_1$ $Y_1$

$X_2$ $Y_2$

$\vdots$

$X_N$ $Y_N$

输出格式

输出圣诞老人需要行走的最小距离。只要输出值与真实值的绝对误差或相对误差不超过$10^{−6}$，即视为正确。

样例输入1

3 2
1 1
3 1
1 2
3 2

样例输出1

9.236067977499790

上图中，红色圆圈代表圣诞老人的家，带数字的圆圈代表对应编号孩子的家。

考虑圣诞老人按以下方式行动：

1. 带上两份礼物离开家；
2. 前往孩子1的家并送出一份礼物；
3. 返回自己的家补充一份礼物；
4. 前往孩子2的家并送出一份礼物；
5. 前往孩子3的家并送出一份礼物；
6. 返回自己的家。

此时圣诞老人行走的总距离为$2+2+1+2+\sqrt{5}=7+\sqrt{5}=9.236\dots$，这是最小距离。

样例输入2

2 1
0 1
-1 1
1 1

样例输出2

4.000000000000000

样例输入3

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

样例输出3

11347715738.116592407226562