Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Demand for electricity grew rapidly in the country over recent years, and is projected to grow even faster in the next twenty years. To cope with this increase in demand, the government is planning 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-generation plants (hydroelectric and nuclear). ICPC’s plants are connected by power lines that cross the country. Each power line connects two distinctpower plants and is constructed in a straight line. A power path is a sequence of power lines $l_1, l_2, ...., l_m$, with each power line $l_i$ connecting directly plants $p_{i−1}$ and $p_i$, such that any two consecutive power lines $l_i$ and $l_{i + 1}$ are linked to a common power plant $p_i$.

The input contains several test cases. The first line of a test case contains two integers $N$ and $C$ indicating respectively the total number of power plants owned by ICPC $(1 \leq N \leq 10000)$ and the minimum total capacity, in MW, that every new company must have $(1 \leq C \leq 10000)$. Power plants are identified by integers from $1$ to $N$; plant $1$ was the first to be built, plant $2$ the second to be built, and so on. Each of the next $N$ lines describes a power plant; the first line describes power plant $1$, the second line describes power plant $2$, and so on. Each description consists of three integers $X$, $Y$ and $P$, where $(X, Y)$ is the plant location ($0 \leq X \leq 1000$ and $0 \leq Y \leq 1000$) and $P$ is the plant capacity $(1 \leq P \leq 1000)$. Plants were built at different locations (that is, no two plants have the same location). The end of input is indicated by $N = C = 0$.

For each test case in the input your program must produce one line of output, containing only one integer: the largest number of new companies that can be created in the privatization process.