You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 ROIR 2023 D2T1。

用于铺设地铁隧道的盾构机有 $n$ 个发动机。所有发动机是并联的，所以所有发动机两端的电压都相同。

每个发动机有两种模式，假设所有发动机接收到的电压都为 $x$，则当 $x\le z_i$ 时第 $i$ 个发动机在第一模式下工作，否则它在第二模式下工作。

第 $i$ 个发动机在第一模式下的单位电流为 $a_i$，在第二模式下的单位电流为 $b_i$。所以，根据 $P=UI$，当发动机处于第一模式时，每增加 $1$ 单位电压，其功率增加 $a_i$ 单位；当发动机处于第二模式时，每增加 $1$ 单位电压，其功率增加 $b_i$ 单位。换句话说，当电压为 $x$ 单位电压，如果第 $i$ 个发动机处于第一模式下，它以 $a_i\times x$ 的单位功率运行；如果处于第二模式下，它以 $a_i\times z_i + b_i\times(x - z_i)$ 的单位功率运行。

题目描述

最少需要提供多大的电压（电压需要是整数），才能使所有发动机的总功率大于或等于 $p$？

输入格式

第一行输入两个整数 $n$ 和 $p$。

接下来的 $n$ 行，每行包含三个整数 $z_i,a_i,b_i$。

输出格式

输出一个整数表示最小电压。

1 6
4 1 2

5

3 15
2 3 3
4 2 1
5 2 2

3

提示

本题使用捆绑测试。

子任务编号	分值	特殊性质
$1$	$20$	$n=1$
$2$		$a_i,b_i\le100,p\le10^5$
$3$		所有 $z_i$ 均相等
$4$		$n\le2$
$5$

对于 $100\%$ 的数据，$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$。