Problem Background

Translated from ROIR 2023 D2T1.

A shield machine used for laying subway tunnels has $n$ engines. All engines are connected in parallel, so they all receive the same voltage.

Each engine has two modes. Assuming all engines receive a voltage of $x$, the $i$-th engine operates in the first mode when $x \leq z_i$, otherwise it operates in the second mode.

The $i$-th engine has a unit current of $a_i$ in the first mode and $b_i$ in the second mode. Therefore, according to $P = UI$, when the engine is in the first mode, each additional unit of voltage increases its power by $a_i$ units; when the engine is in the second mode, each additional unit of voltage increases its power by $b_i$ units. In other words, when the voltage is $x$ units, if the $i$-th engine is in the first mode, it operates at a power of $a_i \times x$ units; if it is in the second mode, it operates at a power of $a_i \times z_i + b_i \times (x - z_i)$ units.

Problem Description

What is the minimum voltage (which must be an integer) that needs to be provided to ensure that the total power of all engines 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 a single integer representing the minimum voltage.

Sample Input and Output

Sample Input #1

1 6
4 1 2

Sample Output #1

5

Sample Input #2

3 15
2 3 3
4 2 1
5 2 2

Sample Output #2

3

Notes

This problem uses bundled test cases.

For $100\%$ of the data, $1 \leq n \leq 100, 1 \leq p \leq 10^{12}, 1 \leq z_i \leq 10^9, 1 \leq a_i, b_i \leq 10^4$.

见题面 Input 部分

见题面 Output 部分