Metro Construction

The drilling rig Megabur 2022, used to dig subway tunnels in Bytesburg, has $n$ engines. All engines receive the same integer voltage $x$.

Each engine has two modes. When voltage $x$ is supplied, engine $i$ works in the first mode if $x \le z_i$, and in the second mode if $x > z_i$.

Engine $i$ is described by its specific power $a_i$ in the first mode and $b_i$ in the second mode. In the first mode, each unit increase of voltage raises the engine's power by $a_i$. In the second mode, each unit increase raises it by $b_i$. So with voltage $x$, the power of engine $i$ is $a_i x$ in the first mode and $a_i z_i + b_i(x - z_i)$ in the second mode.

The total power of the engines must be at least $p$ to dig the tunnel. Find the minimum integer voltage that makes the total power greater than or equal to $p$.

The first line contains integers $n$ and $p$ ($1 \le n \le 100$, $1 \le p \le 10^{12}$).

Each of the next $n$ lines contains three integers $z_i$, $a_i$, $b_i$ ($1 \le z_i \le 10^9$, $1 \le a_i, b_i \le 10^4$).

Print one integer, the minimum voltage that makes the total power at least $p$.