题目背景

用于铺设地铁隧道的盾构机有 $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

样例输入 #1

1 6
4 1 2

样例输出 #1

5

样例 #2

样例输入 #2

3 15
2 3 3
4 2 1
5 2 2

样例输出 #2

3

提示

对于 $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$。