Bitstock

Mirko is hooked on Bitstock, an MMORPG where players buy shares. The market offers exactly $N$ types of shares, and Mirko can buy any amount of any type at any moment. One share of type $i$ costs $c_i$ kuna and, from the moment he buys it, produces $g_i$ kuna per second. Shares can also be bought in real amounts, as long as the amount is positive. For example, if Mirko buys $0.7$ shares of $A$, they produce $0.21 g_A$ kuna over the next $0.3$ seconds.

The twist in Bitstock is that some shares support other shares, and a supported share can be bought at half price. If $A$ supports $B$ and $C$, then $1$ share of $A$ that Mirko owns lets him buy $0.7$ shares of $B$ and $0.3$ shares of $C$ at half price. That share of $A$ cannot finance any further purchase afterwards, although it keeps producing money. In other words, one owned share finances at most $1$ share in total among the types it supports. A share bought at half price supports its own types in exactly the same way. Every type is supported by at most one type, and no type supports itself, directly or indirectly.

Money is available for new purchases the moment it is produced. The goal is to reach a profit of $P$ kuna per second in the shortest time. Mirko starts with $E$ kuna and owns no shares.

The first line contains the number of share types $N$, the starting amount $E$, and the target profit rate $P$ ($1 \le N \le 1000$, $1 \le E, P \le 10^9$).

Each of the next $N$ lines contains the price $c_i$, the profit per second $g_i$, and the number $p_i$ of the share type that supports type $i$ ($1 \le c_i \le 10^9$, $0 \le g_i \le 10^9$, $0 \le p_i \le N$). A value $p_i = 0$ means no type supports type $i$. At least one $g_i$ is positive.

Print the minimum time in seconds needed to reach a profit of $P$ kuna per second. Round the value up to an integer. For example, if $17.2$ seconds are needed, print $18$. If the starting money reaches the target immediately, print $0$.

The input is such that the exact minimum time is $0$ or differs from every integer by at least $10^{-6}$.