주문 시전

주문을 시전하는 것은 연속적인 과정이다. 시전자는 일정한 양의 에너지(마나 단위로 측정)를 가지고 시작하며, 이 에너지를 소모해 주문에 원소를 소환할 수 있다. 각 원소는 에너지를 소모하는 즉시 임의의 양만큼 소환되며, 소환되는 순간부터 주문의 일부가 되어 위력(초당 마나로 측정)을 제공한다. 이 위력은 시간이 지남에 따라 에너지를 축적시키고, 축적된 에너지는 다시 추가 원소를 소환하는 데 쓰인다. 우리는 주문의 총 위력이 목표치에 도달할 때까지 이 과정을 계속한다.

이 과정에는 한 가지 특징이 있는데, 숙련된 시전자는 이를 이용해 주문을 더 효율적으로 시전한다. 각 원소는 최대 하나의 부모 원소를 가질 수 있으며, 부모 원소가 이미 존재하면 그 소환을 보조하여 평소의 절반 에너지로 소환할 수 있게 해 준다. 예를 들어 원소 $A$가 원소 $B$와 원소 $C$를 보조한다면, 먼저 원소 $A$ 1단위를 정상 비용으로 소환한 뒤 원소 $B$ 0.5단위와 원소 $C$ 0.5단위를 절반 비용으로 소환할 수 있다. 만약 이어서 원소 $C$를 0.5단위 더 소환한다면, 그 부분은 다시 정상 에너지 비용이 든다. 이미 존재하는 $A$ 1단위가 다른 원소들을 보조하는 데 모두 쓰였기 때문이다. 즉 부모 원소 1단위는 자신의 자식 원소들에게 (여러 자식에 걸쳐 합산하여) 최대 1단위만큼의 절반 비용 보조를 제공한다. 세 원소 모두 자신의 위력을 온전히 주문에 기여하며, 보조 행위는 위력 출력에 어떤 영향도 주지 않고 원소를 소모하지도 않는다.

초기 에너지, 목표 위력, 그리고 소환 가능한 주문 원소들의 설명이 주어질 때, 목표 위력에 최소 시간 안에 도달하도록 주문을 시전하는 방법을 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 세 개의 정수 $N$, $E$, $P$가 공백으로 구분되어 있는 한 줄로 시작하며, 각각 원소의 개수, 시작 에너지(마나), 목표 위력(초당 마나)을 나타낸다. 이어서 $N$개의 줄이 주어지고, 그중 $i$번째 줄은 세 정수 $e_i$, $p_i$, $\mathrm{parent}_i$로 원소 $i$를 설명한다. 각각 소환에 드는 에너지 비용, 위력 출력, 그리고 부모 원소의 번호(1부터 시작; 부모가 없으면 $\mathrm{parent}_i = 0$)이다.

제약 조건은 다음과 같다.

• $1 \le N \le 1000$, $1 \le E \le 10^9$, $1 \le P \le 10^9$.
• 모든 $i$에 대해 $1 \le e_i \le 10^9$, $0 \le p_i \le 10^9$, $0 \le \mathrm{parent}_i \le N$.
• 적어도 하나의 $p_i$는 양수이다.
• 어떤 원소도 자기 자신의 조상이 아니다. 다시 말해, 어떤 원소도 직접적으로든 간접적으로든 자기 자신을 보조할 수 없다.

입력은 $N = E = P = 0$인 케이스로 끝나며, 이 케이스는 처리하지 않는다.

각 테스트 케이스마다, 목표 위력에 도달하는 데 필요한 최소 시간(초)을 가장 가까운 정수로 올림하여 한 줄에 하나의 정수로 출력한다.