비트스톡

미르코는 주식을 사고파는 MMORPG 비트스톡에 푹 빠져 있다. 시장에는 정확히 $N$가지 주식이 있고, 미르코는 아무 때나 원하는 주식을 원하는 만큼 살 수 있다. $i$번 주식 한 주의 가격은 $c_i$쿠나이고, 사는 순간부터 초당 $g_i$쿠나를 벌어 준다. 주식은 실수 단위로도 살 수 있다. 다만 그 양은 양수여야 한다. 예를 들어 $A$ 주식을 $0.7$주 사면 그 주식은 다음 $0.3$초 동안 $0.21 g_A$쿠나를 번다.

비트스톡의 특징은 어떤 주식이 다른 주식을 지원한다는 점이다. 지원받는 주식은 반값에 살 수 있다. $A$가 $B$와 $C$를 지원한다면, 가지고 있는 $A$ 주식 $1$주로 $B$를 $0.7$주, $C$를 $0.3$주 반값에 살 수 있다. 이렇게 쓴 $A$ 주식으로는 더 이상 다른 구매를 지원하지 못한다. 물론 그 주식은 계속 돈을 번다. 즉 가지고 있는 주식 $1$주는 자신이 지원하는 주식을 모두 합쳐 $1$주까지만 반값에 사게 해 준다. 반값에 산 주식도 똑같은 방식으로 자신이 지원하는 주식을 지원한다. 각 주식은 많아야 한 종류의 주식에게 지원받고, 직접이든 간접이든 자기 자신을 지원하지 않는다.

벌어들인 돈은 생기는 즉시 다시 주식을 사는 데 쓸 수 있다. 목표는 초당 $P$쿠나의 수익을 가장 짧은 시간 안에 만드는 것이다. 미르코는 처음에 $E$쿠나를 가지고 있고, 주식은 하나도 없다.

첫째 줄에 주식의 종류 수 $N$, 처음 가진 금액 $E$, 목표 수익률 $P$가 주어진다 ($1 \le N \le 1000$, $1 \le E, P \le 10^9$).

다음 $N$개 줄의 $i$번째 줄에는 $i$번 주식의 가격 $c_i$, 초당 수익 $g_i$, 그리고 $i$번 주식을 지원하는 주식의 번호 $p_i$가 주어진다 ($1 \le c_i \le 10^9$, $0 \le g_i \le 10^9$, $0 \le p_i \le N$). $p_i = 0$은 $i$번 주식을 지원하는 주식이 없다는 뜻이다. $g_i$ 중 적어도 하나는 양수다.

초당 $P$쿠나의 수익을 만드는 데 필요한 최소 시간을 초 단위로 출력한다. 값은 올림해서 정수로 적는다. 예를 들어 $17.2$초가 필요하면 $18$을 출력한다. 처음 가진 돈만으로 목표를 바로 달성하면 $0$을 출력한다.

정확한 최소 시간이 $0$이거나 모든 정수와 $10^{-6}$ 이상 차이가 나도록 입력이 주어진다.