P10098 [ROIR 2023] Subway Construction (Day 2)

Translated from [ROIR 2023 D2T1](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day2.pdf). A shield tunneling machine used to build subway tunnels has $n$ motors. All motors are connected in parallel, so the voltage across all motors is the same. Each motor has two modes. Suppose the voltage received by all motors is $x$. Then, for the $i$-th motor, if $x \le z_i$, it works in the first mode; otherwise, it works in the second mode. The unit current of the $i$-th motor is $a_i$ in the first mode and $b_i$ in the second mode. Therefore, by $P = UI$, when the motor is in the first mode, each increase of $1$ unit of voltage increases its power by $a_i$ units; when it is in the second mode, each increase of $1$ unit of voltage increases its power by $b_i$ units. In other words, when the voltage is $x$, if the $i$-th motor is in the first mode, it runs at power $a_i \times x$; if it is in the second mode, it runs at power $a_i \times z_i + b_i \times (x - z_i)$.

What is the minimum voltage that must be provided (the voltage must be an integer) so that the total power of all motors is greater than or equal to $p$?

The first line contains two integers $n$ and $p$. The next $n$ lines each contain three integers $z_i, a_i, b_i$.

Output one integer, the minimum voltage.

This problem uses bundled testdata. | Subtask ID | Points | Special Property | | :----------: | :----------: | :----------: | | $1$ | $20$ | $n = 1$ | | $2$ | $20$ | $a_i, b_i \le 100, p \le 10^5$ | | $3$ | $20$ | All $z_i$ are equal | | $4$ | $20$ | $n \le 2$ | | $5$ | $20$ | | For $100\%$ of the data, $1 \le n \le 100$, $1 \le p \le 10^{12}$, $1 \le z_i \le 10^9$, $1 \le a_i, b_i \le 10^4$. Translated by ChatGPT 5