Power Generation

Demand for electricity has grown rapidly in the country over recent years, and it is projected to grow even faster over the next twenty years. To cope with this increase, the government plans to privatize the country's electricity power-generation sector, ending the monopoly of the state-owned company ICPC (Independent Circuit Power Corporation).

ICPC owns a set of power plants (hydroelectric and nuclear). The plants are connected by power lines that cross the country. Each power line connects two distinct plants and is a straight segment. A power path is a sequence of power lines $l_1, l_2, \ldots, l_m$ in which each line $l_i$ directly connects plants $p_{i-1}$ and $p_i$, and any two consecutive lines $l_i$ and $l_{i+1}$ share a common plant $p_i$.

The plants were built over several years, one at a time, because of budget limits. Also because of budget limits, whenever a new plant was built, exactly one new power line was constructed to attach it to the existing system. That new line always connected the new plant to the nearest plant already in the system, measured by Euclidean distance. If more than one such plant was at the minimum distance, the oldest (earliest built) one was chosen.

The goal of the privatization is to split the ICPC system into smaller companies. Each company owns a set of plants, and every plant is owned by exactly one company. After privatization ICPC ceases to exist and only the new companies own plants. The split must satisfy:

• The total capacity of every new company must be at least $C$, a value in MW (megawatts) set by the government. The total capacity of a set of plants is the sum of the plants' capacities.
• For any two plants owned by a company, every power path between them must pass only through plants owned by that same company.

Determine the largest number of new companies that can be created in the privatization process.

The input contains several test cases. The first line of a test case has two integers $N$ and $C$: the total number of power plants owned by ICPC ($1 \le N \le 10000$) and the minimum total capacity, in MW, that every new company must have ($1 \le C \le 10000$). Plants are identified by integers from $1$ to $N$; plant $1$ was built first, plant $2$ second, and so on. Each of the next $N$ lines describes one plant: the first of these lines describes plant $1$, the second describes plant $2$, and so on. Each description has three integers $X$, $Y$, and $P$, where $(X, Y)$ is the plant's location ($0 \le X \le 1000$ and $0 \le Y \le 1000$) and $P$ is its capacity ($1 \le P \le 1000$). No two plants share the same location. The end of input is indicated by $N = C = 0$.

For each test case, print a single line containing one integer: the largest number of new companies that can be created in the privatization process.