Spellcasting

Casting a spell is a continuous process. You begin with a certain amount of energy (measured in mana), which can be spent to summon elements into the spell. Each element can be summoned in any quantity instantaneously by spending energy, at which point it immediately becomes part of the spell and provides power (measured in mana per second) from then on. This power accumulates energy over time, which can in turn be used to summon additional elements. We continue this process until the total power of the spell reaches the required level.

There is one twist that experienced spellcasters exploit to cast more efficiently. Each element can have at most one parent element, which supports its summoning: if the parent element is already present, the child costs half as much energy as usual. For example, if element $A$ supports element $B$ and element $C$, we could summon 1 unit of element $A$ at full cost first, then summon 0.5 unit of element $B$ and 0.5 unit of element $C$ at half cost. If we then summoned 0.5 more unit of element $C$, that portion would again cost full energy, because the 1 unit of element $A$ is already fully supporting other elements. In other words, one unit of a parent element provides at most 1 unit of half-cost support to its children in total (shared across all of its children). All elements contribute their full power to the spell; supporting does not affect power output in any way, nor does it consume an element.

Given an initial amount of energy, a target amount of power, and a description of the spell elements available for summoning, determine how to cast a spell that reaches the target power in the minimum amount of time.

The input consists of multiple test cases. Each test case begins with a line containing three space-separated integers $N$, $E$, and $P$: the number of elements, the starting energy (in mana), and the target power (in mana per second). This is followed by $N$ lines, the $i$-th of which describes element $i$ by three space-separated integers $e_i$, $p_i$, and $\mathrm{parent}_i$: the energy cost to summon it, its power output, and the index of its parent element (1-indexed; $\mathrm{parent}_i = 0$ if element $i$ has no parent).

Constraints:

• $1 \le N \le 1000$, $1 \le E \le 10^9$, $1 \le P \le 10^9$.
• $1 \le e_i \le 10^9$, $0 \le p_i \le 10^9$, and $0 \le \mathrm{parent}_i \le N$ for all $i$.
• At least one $p_i$ is positive.
• No element is its own ancestor; that is, no element can support itself, directly or indirectly.

The input is terminated by a case with $N = E = P = 0$, which should not be processed.

For each test case, print a single line containing a single integer: the minimum number of seconds required to reach the target power, rounded up to the nearest integer.