题目内容

维修工要给n个客户更换设备，为每个用户更换一个设备。维修工背包内最多装k个设备，如果背包里有设备可以直接前往下一个客户更换或回公司补充设备，没有则需要回公司取设备。这些客户有优先级，维修工需要按照优先级给客户更换设备，优先级level用数字表示，数字小的优先级高。维修工从公司出发，给n个客户更换设备，最后再返回公司。请计算维修工完成这项工作所需要经历的最短总距离是多少。维修工可以走斜线，请参考样例1图示。

输入描述

第一行：两个正整数n,k(1 ≤ k ≤ n ≤ 2000)，表示客户数和维修工背包容量。
第二行：两个正整数x,y，用空格分隔(1 ≤ x,y≤ 10^6)，表示公司的坐标。
接下来n行：每行三个正整数xi,yi,leveli，用空格分隔，(1 ≤ xi,yi ≤ 10^6, 1 ≤ leveli ≤ n)，(xi,yi)表示第i个客户的位置坐标，leveli表示第i个客户的优先级。保证所有客户优先级不同，客户和公司坐标不会重叠。

输出描述

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

样例1

输入

3 2
0 0
1 1 1
2 2 2
3 3 3

输出

9.2

解释

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

样例2

输入

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

输出

11.3

解释

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