#3736. 「COCI 2015.11」DRŽAVA

题目描述

题目译自 COCI 2015-2016 CONTEST #2 T6「DRŽAVA」。

一个遥远的国家刚刚举行了选举，新首相当选了。目前，这个国家没有一条公路，所以首相决定用双向公路把国内的城市连接起来，组成县，使国家现代化。

这个国家共有 $N$ 个城市，每个县由一个或多个城市组成，两个城市将位于同一个县，当且仅当使用新建的道路可以从一个城市到达另一个城市。这些城市在二维坐标系中用点来表示，两个城市之间的道路表示为连接两个城市所在点的线段。这条路的长度等于以公里为单位的线段的长度。

该国目前正遭受经济衰退，因此首相决定，由于缺乏预算，他们将不修建超过 $D$ 公里的道路。此外，如果至少有一个县存在一个非空子县（可以包括该县的所有城市），使得子县内的居民总数可以被 $K$ 整除，首相就会高兴。例如，如果 $K=4$，一个县的城市分别有 $3,5,7$ 个居民，首相就会高兴，因为前两个城市的居民总数等于 $8$。

请你确定最小的 $D$ 来帮助首相降低成本，使得首相感到高兴。

输入格式

第一行包含两个整数 $N,K$。

接下来 $N$ 行，每行三个整数 $x_i,y_i,k_i$，分别表示这个城市的坐标和这个城市的人口。

输出格式

一行一个实数，表示最小的 $D$，四舍五入保留三位小数。

---

样例 1

输入

3 3
0 4 4
1 5 1
2 6 1

输出

1.414

只有当所有城市都在同一个县里首相才能高兴，所以最小的 $D$ 为 $1.414$。

---

样例 2

输入

6 11
0 0 1
0 1 2
1 0 3
1 1 4
5 5 1
20 20 10

输出

5.657

当前五个城市都在同一个县里首相才能高兴，且此时 $D$ 是最小的，所以最小的 $D$ 为 $5.657$。

---

样例 3

输入

6 5
20 20 9
0 0 3
0 1 1
10 0 1
10 1 6
12 0 3

输出

2.000

---

数据范围与提示

对于 $40\%$ 的数据，$1\le N\le10^3$；

对于 $100\%$ 的数据，$1\le N\le5\times10^4$，$1\le K\le30$，$0\le x_i,y_i,k_i\le10^8$。