Description

A distant country has just held an election, and a new prime minister has been elected. Currently, there are no roads in this country, so the prime minister decided to connect the cities with two-way roads to form counties and modernize the country.

There are $N$ cities in the country. Each county consists of one or more cities. Two cities are in the same county if and only if one can travel from one city to the other using the newly built roads. The cities are represented as points in a 2D coordinate system, and a road between two cities is represented as a line segment connecting the corresponding points. The length of a road equals the length of this segment in kilometers.

The country is currently suffering an economic recession, so the prime minister decided that, due to a lack of budget, they will not build roads longer than $D$ kilometers. Also, the prime minister will be happy if there exists at least one county that has a non-empty sub-county (which may include all cities of that county) such that the total population in the sub-county is divisible by $K$. For example, if $K=4$ and a county has cities with populations 3, 5, and 7, the prime minister will be happy because the total population of the first two cities is 8.

You need to determine the minimum $D$ to help the prime minister reduce costs so that the prime minister becomes happy.

Input Format

The first line contains two integers $N, K$.

The next $N$ lines each contain three integers $x_i, y_i, k_i$, representing the coordinates of the city and its population.

Output Format

Output one real number in a single line: the minimum $D$, rounded to three decimal places.

3 3
0 4 4
1 5 1
2 6 1

1.414

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

5.657

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

2.000

Hint

[Sample 1 Explanation]

The prime minister can be happy only when all cities are in the same county, so the minimum $D$ is $1.414$.

[Sample 2 Explanation]

The prime minister can be happy only when the first five cities are in the same county, and in this case $D$ is minimal, so the minimum $D$ is $5.657$.

[Constraints]

For $40\%$ of the testdata, $1 \le N \le 10^3$.

For $100\%$ of the testdata, $1 \le N \le 5 \times 10^4$, $1 \le K \le 30$, $0 \le x_i, y_i, k_i \le 10^8$.

[Notes]

The scoring for this problem follows the original problem, with a full score of 160.

This problem is translated from COCI 2015-2016 CONTEST #2 T6 DRŽAVA.

Translated by ChatGPT 5