Highways and Counties

Time limit2sMemory limit64 MB

Summary

Find the smallest road length limit so cities joined by shorter roads form a group whose populations hold a subset summing to a multiple of K.

Level: Hard9 of 10
Topics: Minimum spanning tree, Dynamic programming, Union-find, Geometry
Solved: No attempts yet

Problem

A faraway country has $N$ cities. An election just ended and a new prime minister took office. The country has no roads at all yet, so the prime minister decided to modernize it by connecting some cities with two way highways and forming counties. Two cities belong to the same county if you can travel from one to the other along the new roads. Every city belongs to exactly one county, and every county holds at least one city.

The cities are points in a two dimensional coordinate system. A road between two cities is the line segment that joins the two points, and the length of the road is the length of that segment. Lengths are measured in kilometers.

The country is in a recession and the budget is small, so the prime minister will not build a road longer than $D$ kilometers. The prime minister is pleased by small things: he is happy if some county holds a nonempty subset of its cities whose numbers of residents sum to a multiple of $K$ . That subset may be all the cities of the county. For example, if $K = 4$ and a county holds cities with 3, 5 and 7 residents, the prime minister is happy, because the first two cities hold 8 residents together.

Find the smallest $D$ for which the prime minister can build the roads and be happy.

Input

The first line contains the integers $N$ and $K$ ( $1 \le N \le 50000$ , $1 \le K \le 30$ ).

Each of the next $N$ lines contains the integers $x_i$ , $y_i$ , $k_i$ ( $0 \le x_i, y_i, k_i \le 100000000$ ): the $x$ coordinate of a city, the $y$ coordinate of that city, and the number of residents in it. No two cities share the same coordinates. No city has a number of residents divisible by $K$ .

Output

Print on a single line the smallest $D$ for which the prime minister can build the roads and be happy, rounded to three decimal places. The input is always such that an answer exists.

Hint

In the first example the prime minister is happy only when every city lies in one county, and the smallest $D$ that allows it is 1.414.

In the second example the prime minister is happy once the first five cities lie in one county. With $D = 5.657$ he can connect cities 1, 2, 3 and 5 to city 4. Cities 1 through 5 then hold 11 residents in total, which is divisible by 11.

Examples4

Example 1
Input
```
3 3
0 4 4
1 5 1
2 6 1
```
Expected output
```
1.414
```

Example 2

Input

Expected output

5.657

Example 3

Input

Expected output

2.000

Example 4
Input
```
2 2
0 0 1
0 3 1
```
Expected output
```
3.000
```