题目内容

维修工要给$n$个客户更换设备，为每个用户更换一个设备。维修工背包内最多装$k$个设备，如果背包里有设备可以直接前往下一个客户更换或回公司补充设备，没有则需要回公司取设备。

这些客户有优先级，维修工需要按照优先级给客户更换设备，优先级$level$用数字表示，数字小的优先级高。

维修工从公司出发，给$n$个客户更换设备，最后再返回公司。

请计算维修工完成这项工作所需要经历的最短总距离是多少。维修工可以走斜线，请参考样例$1$图示。

输入描述

第一行两个正整数$n,k(1≤k≤n≤2000)$,表示客户数和维修工背包容量。

第二行两个正整数$x,y$，用空格分隔$(1≤x,y≤10^6)$,表示公司的坐标

接下来$n$行每行三个正整数$x_i,y_i,level_i$，用空格分隔,

$(1≤x_i,y_i≤10^6,1≤level_i≤n)$.$(x_i,y_i)$表示第$i$个客户的位置坐标$level_i$表示第$i$个客户的优先级，保证所有客户优先级不同，客户和公司坐标不会重叠，

输出描述

输出最短总距离，结果四舍五入并保留一位小数，例如:$9.0$。

样例1

输入

3 2
1 1
3 1 1
1 2 2
3 2 3

输出

9.2

解释

箭头为最短距离的规划路径:公司 -> 1 -> 公司 -> 2 -> 3 -> 公司

样例2

输入

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

输出

11.3

解释

维修工背包容量是$1$，逐个按优先级为每个客户更换设备，到每个客户单程距离计算为$\sqrt{2}$，往返一个客户距离是$2\sqrt{2}$，总路程为$8\sqrt{2}$ ，最短总距离四会五入后为$11.3$。