Background

Translated from ROIR 2023 D2T1.

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)$.

Problem Description

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$?

Input Format

The first line contains two integers $n$ and $p$.

The next $n$ lines each contain three integers $z_i, a_i, b_i$.

Output Format

Output one integer, the minimum voltage.

1 6
4 1 2

5

3 15
2 3 3
4 2 1
5 2 2

3

Hint

This problem uses bundled testdata.

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