一个遥远的国家有 $N$ 个城市。该国刚刚举行了选举，选出了新的首相。目前，该国一条公路也没有，因此首相决定通过修建一些双向公路连接部分城市来使国家现代化，并以此划分“郡”。如果可以通过新建的公路从一个城市到达另一个城市，则这两个城市属于同一个郡。每个城市都恰好属于一个郡。每个郡由一个或多个城市组成。

城市被表示为二维直角坐标系中的点。两个城市之间的公路表示为连接这两个城市所在点的线段。公路的长度等于该线段的长度（单位：千米）。

该国目前正处于经济衰退期，因此由于预算不足，首相决定不修建长度超过 $D$ 千米的公路。此外，首相很容易因一些小事而感到满足，因此如果至少有一个郡中存在一个非空城市子集（可以包含该郡中的所有城市），使得这些城市居民总数之和能被 $K$ 整除，首相就会感到高兴。例如，如果 $K = 4$，且某个郡中的城市分别有 $3, 5, 7$ 名居民，首相就会感到高兴，因为前两个城市的居民数之和为 $8$（能被 $4$ 整除）。

请通过确定最小的 $D$，使得首相既能修建公路，又能同时因这些小事感到高兴，从而帮助首相削减开支。

输入格式

输入的第一行包含两个整数 $N$ 和 $K$（$1 \le N \le 50\,000$，$1 \le K \le 30$）。

接下来的 $N$ 行，每行包含三个整数 $x_i, y_i, k_i$（$0 \le x_i, y_i, k_i \le 100\,000\,000$），分别代表该城市的 $x$ 坐标、$y$ 坐标以及该城市的居民数量。

输入数据中不会有两个城市具有相同的坐标。此外，不会有任何单个城市的居民数量能被 $K$ 整除。

输出格式

输出的第一行也是唯一的一行，应包含最小的 $D$，使得在满足条件的情况下首相能够感到高兴。输出的 $D$ 四舍五入保留 3 位小数。输入数据保证总是有解。

子任务

对于 $40\%$ 的测试数据，城市数量 $N \le 1000$。

样例

输入样例 1

3 3
0 4 4
1 5 1
2 6 1

输出样例 1

1.414

输入样例 2

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

输出样例 2

5.657

输入样例 3

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

输出样例 3

2.000

说明

样例 1 说明

让首相高兴的唯一方法是所有城市都属于同一个郡。实现这一目标的最小 $D$ 为 $1.414$。

样例 2 说明

如果前 5 个城市在同一个郡中，首相就会高兴。如果 $D = 5.657$，首相可以将城市 1, 2, 3, 5 与城市 4 连接。在这种情况下，城市 1, 2, 3, 4, 5 的居民总数之和将为 $11$，能被 $11$ 整除，因此首相会感到高兴。