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.

题目描述

“Megabur 2022” 钻机用于在 Byteburg 铺设地铁隧道，它有 $n$ 个发动机。钻机的供电方式是所有发动机都接收相同的整数电压 $x$。

每个发动机有两种工作模式，当电压 $x$ 施加到第 $i$ 个发动机时，如果 $x \leq z_{i}$，它在第一模式下工作；如果 $x > z_{i}$，它在第二模式下工作。

第 $i$ 个发动机在第一模式下的单位功率为 $a_{i}$，在第二模式下的单位功率为 $b_{i}$。这意味着，当发动机在第一模式下时，电压每增加 $1$，其功率增加 $a_{i}$；在第二模式下，功率增加 $b_{i}$。换句话说，当电压为 $x$ 时，如果第 $i$ 个发动机在第一模式下工作，其功率为 $a_{i} x$；如果在第二模式下工作，其功率为 $a_{i} z_{i} + b_{i} (x - z_{i})$。

为了铺设隧道，发动机的总功率必须不小于 $p$。需要施加的最小整数电压是多少，才能使发动机的总功率大于或等于 $p$？

输入格式

第一行输入包含两个整数 $n$ 和 $p$ $(1 \leq n \leq 100, 1 \leq p \leq 10^{12})$。

接下来的 $n$ 行描述发动机，每行包含三个整数 $z_{i}, a_{i}, b_{i}$ $(1 \leq z_{i} \leq 10^9, 1 \leq a_{i}, b_{i} \leq 10^4)$。

输出格式

输出一个整数，表示需要施加的最小电压。

1 6
4 1 2

5

3 15
2 3 3
4 2 1
5 2 2

3

数据范围与提示

详细子任务附加限制及分值如下表所示。