Problem Description

A distant country has just held an election, and a new prime minister has been elected. Currently, the country has no roads, so the prime minister has decided to connect the cities within the country with bidirectional roads to form counties, aiming to modernize the nation.

The country has a total of $N$ cities. Each county consists of one or more cities. Two cities will be in the same county if and only if a newly built road allows travel from one city to the other. These cities are represented as points in a two-dimensional coordinate system, and the roads between two cities are represented as the line segment connecting the points of the two cities. The length of the road is equal to the length of the segment in kilometers.

The country is currently experiencing an economic recession, so the prime minister has decided that due to budget constraints, they will not build roads longer than $D$ kilometers. Additionally, the prime minister will be happy if at least one county has a non-empty sub-county (which can include all cities of the county) such that the total population within 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.

Determine the smallest $D$ to help the prime minister reduce costs while ensuring the prime minister is happy.

Input Format

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

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

Output Format

Output a single real number, representing the smallest $D$, rounded to three decimal places.

Sample Input and Output

Sample Input #1

3 3
0 4 4
1 5 1
2 6 1

Sample Output #1

1.414

Sample Input #2

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

Sample Output #2

5.657

Sample Input #3

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

Sample Output #3

2.000

Notes

[Sample 1 Explanation]

The prime minister will only be happy if all cities are in the same county, so the smallest $D$ is $1.414$.

[Sample 2 Explanation]

The prime minister will be happy if the first five cities are in the same county, and this is the smallest $D$, so the smallest $D$ is $5.657$.

[Data Range]

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

For $100\%$ of the data, $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]

This problem's scoring is based on the original contest, with a maximum score of 160.

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

见题面 Input 部分

见题面 Output 部分