발전소 민영화

최근 몇 년간 이 나라의 전력 수요가 빠르게 늘었고, 앞으로 20년 동안에는 더욱 빠르게 늘어날 것으로 예상된다. 이 수요 증가에 대응하기 위해 정부는 국영 기업 ICPC(Independent Circuit Power Corporation)의 독점을 끝내고 전력 생산 부문을 민영화하려 한다.

ICPC는 여러 발전소(수력 및 원자력)를 보유하고 있다. 발전소들은 전국을 가로지르는 송전선으로 연결되어 있다. 각 송전선은 서로 다른 두 발전소를 직선으로 잇는다. 송전 경로란 송전선 $l_1, l_2, \ldots, l_m$ 의 나열로서, 각 송전선 $l_i$ 는 발전소 $p_{i-1}$ 과 $p_i$ 를 직접 잇고, 연속한 두 송전선 $l_i$ 와 $l_{i+1}$ 은 공통 발전소 $p_i$ 를 공유한다.

발전소는 예산 제약 때문에 여러 해에 걸쳐 한 번에 하나씩 지어졌다. 역시 예산 제약 때문에, 새 발전소를 지을 때마다 그 발전소를 기존 시스템에 연결하는 송전선은 정확히 하나만 건설되었다. 새 송전선은 항상 새로 지은 발전소를, 이미 시스템에 있는 발전소 중 (유클리드 거리 기준) 가장 가까운 발전소와 연결했다. 그런 발전소가 둘 이상이면(즉 최소 거리에 있는 발전소가 둘 이상이면) 가장 먼저 지어진(가장 오래된) 발전소를 선택했다.

민영화의 목표는 ICPC 전력 생산 시스템을 더 작은 여러 회사로 나누는 것이다. 각 회사는 발전소들의 집합을 소유하며, 각 발전소는 정확히 한 회사만 소유한다. 민영화가 끝나면 ICPC는 사라지고 새 회사들만 발전소를 소유한다. 발전소를 새 회사들에게 나누는 방식은 다음 제약을 지켜야 한다.

• 모든 새 회사의 총 용량은 최소 $C$ 이상이어야 한다. 여기서 $C$ 는 정부가 정한 값(단위 MW, 메가와트)이다. 발전소 집합의 총 용량은 그 발전소들의 용량의 합이다.
• 한 회사가 소유한 임의의 두 발전소 사이의 모든 송전 경로는 그 회사가 소유한 발전소만을 지나야 한다.

민영화 과정에서 만들 수 있는 새 회사의 최대 개수를 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $N$ 과 $C$ 가 주어진다. $N$ 은 ICPC가 보유한 발전소의 총 수($1 \le N \le 10000$), $C$ 는 모든 새 회사가 가져야 하는 최소 총 용량(MW, $1 \le C \le 10000$)이다. 발전소는 $1$ 번부터 $N$ 번까지의 정수로 구분한다. 발전소 $1$ 번이 가장 먼저, $2$ 번이 그다음 순서로 지어졌다. 이어지는 $N$ 개의 줄은 각 발전소를 설명하며, 첫 줄은 발전소 $1$ 번, 둘째 줄은 발전소 $2$ 번을 나타내는 식이다. 각 줄에는 세 정수 $X$, $Y$, $P$ 가 주어진다. $(X, Y)$ 는 발전소의 위치($0 \le X \le 1000$, $0 \le Y \le 1000$)이고, $P$ 는 발전소의 용량($1 \le P \le 1000$)이다. 어떤 두 발전소도 같은 위치에 있지 않다. 입력의 끝은 $N = C = 0$ 인 줄로 나타낸다.

각 테스트 케이스마다 한 줄을 출력한다. 그 줄에는 민영화 과정에서 만들 수 있는 새 회사의 최대 개수를 나타내는 정수 하나만 출력한다.