Problem I
Država

A distant country has $N$ cities in it. The elections were just held in this country, so the new prime minister was elected. Currently, there is not a single road in this country, so the prime minister decided to modernize the country by connecting some cities with two-way highways and form counties. Two cities will be located in the same county if it is possible to get to one city from the other using the newly built roads. Each city will be located in exactly one county. Each county consists of one or more cities.

The cities are represented as points in a two-dimensional coordinate system. The road between two cities is represented as a line segment connecting two points where the cities are located. The length of the road is equal to the length of the line segment in kilometers.

The country is currently suffering from recession, so the prime minister decided that, because of the lack of budget, they will not build roads longer than $D$ kilometers. Additionally, the prime minister is happy about the small things, so he will be happy if, in at least one county, there exists a nonempty subset of cities (it can include all cities in the county) where the total sum of residents is divisible by $K$. For instance, if $K = 4$ and there is a county with cities that have $3$, $5$, $7$ residents respectively, the prime minister will be happy because the sum of residents in the first two cities is equal to $8$.

Help the prime minister in cutting the costs by determining the minimal $D$ such that the prime minister can build roads and be happy about the small things at the same time.

Input

The first line of input contains the integers $N$ and $K$ ($1 \leq N \leq 50\, 000$, $1 \leq K \leq 30$). Each of the following $N$ lines contains three integers $x_ i$, $y_ i$, $k_ i$ ($0 \leq x_ i, y_ i, k_ i \leq 100\, 000\, 000$), that represent the x coordinate of the city, the y coordinate and the number of residents in that city, respectively. There will not be two cities with the same coordinates in the input data. Additionally, there will not be a single city with the number of residents divisible by $K$.

Output

The first and only line of output must contain the minimal $D$ such that it is possible to build roads with the condition that the prime minister is happy. An answer accurate to $3$ decimal places will be accepted. The input data will be such that there is always a solution.

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