Minimum Road Length for Divisible County Subset

In a distant country, there are N cities located in the plane. The newly elected prime minister wishes to modernize the nation by connecting cities with bidirectional roads. However, due to budget constraints, only roads with length at most D kilometers will be constructed.

A county is defined as a set of one or more cities which are connected by these roads; that is, two cities belong to the same county if and only if one can travel from one to the other using only roads of length at most D. Each city also has an associated population.

The prime minister will be happy if there exists at least one county for which some nonempty subset of its cities has a total population divisible by K. In other words, for at least one county, there exists a nonempty subset S such that

\(\sum_{i\in S} p_i \equiv 0 \pmod{K}\)

Your task is to determine the minimum D (in kilometers) that makes the prime minister happy.

inputFormat

The input begins with two integers N and K, where N is the number of cities and K is the divisor.

This is followed by N lines, each containing three numbers: x, y, and p, where (x, y) are the coordinates of a city and p is its population.

outputFormat

Output the minimum value D (in kilometers) that makes the prime minister happy. The answer should be printed accurate to 6 decimal places. If it is impossible to achieve the condition, output -1.

sample

3 4
0 0 3
0 3 5
4 0 7

3.000000