该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

程老师帮一家饮品店算账。店里的操作台上并排摆着 $m$ 台豆浆机，早上开门时，这些机器同时按下开关，一直开到当天备货完成为止。每台机器的型号不一样，参数有三个：预热时间 $w_i$、产出速度 $r_i$、累计产能上限 $cap_i$。

每台机器按下开关后的头 $w_i$ 分钟是预热，这期间一杯豆浆都不出。预热结束后机器进入产出状态，从第 $w_i + 1$ 分钟开始，每过一分钟产出 $r_i$ 杯，一分钟一分钟地出，中间不停顿。机器还有一个累计产能上限 $cap_i$：从按下开关算起，当这台机器累计产出的杯数达到 $cap_i$ 杯时，它立刻停机，此后一分钟也不再产出。预热时间 $w_i$ 可以为 $0$，那就是一开机就能出豆浆。

店主要求当天至少备出 $T$ 杯。程老师要算的是：从按下开关那一刻起，最少要过多少分钟，操作台上的产出总量才能至少达到 $T$ 杯。时间按整分钟计，如果第 $t$ 分钟结束时产出总量首次不小于 $T$，答案就是 $t$。

输入格式

从文件 soy.in 中读入数据。

第一行两个整数 $m, T$。

接下来 $m$ 行，每行三个整数 $w_i, r_i, cap_i$，依次表示第 $i$ 台机器的预热时间、产出速度、累计产能上限。

输出格式

输出到文件 soy.out 中。

一行一个整数，表示产出总量至少达到 $T$ 杯所需的最少分钟数。

数据范围

对于所有测试数据，保证：

• $1 \le m \le 10^5$；
• $0 \le w_i \le 10^9$；
• $1 \le r_i \le 10^4$；
• $1 \le cap_i \le 10^{12}$；
• $1 \le T \le 10^{12}$；
• $\sum_{i=1}^{m} cap_i \ge T$，即备货一定能在有限时间内完成。

特殊性质 A：每台机器的预热时间都是 $0$ 分钟。

特殊性质 B：每台机器的累计产能上限 $cap_i$ 都不小于 $T$。

2 10
1 2 5
0 1 100

5

1 7
3 4 8

5

样例解释

样例 1：第 $1$ 分钟结束时，$1$ 号机还在预热，$2$ 号机产出 $1$ 杯，共 $1$ 杯；第 $2$ 分钟结束时 $1$ 号机产出 $2$ 杯、$2$ 号机再出 $1$ 杯，共 $4$ 杯；第 $3$ 分钟结束时共 $7$ 杯；第 $4$ 分钟结束时 $1$ 号机累计已经产到 $5$ 杯上限、就此停机，这一分钟只有 $2$ 号机出 $1$ 杯，共 $9$ 杯；第 $5$ 分钟结束时 $2$ 号机再出 $1$ 杯，共 $10$ 杯，首次不小于 $10$。

样例 2：前 $3$ 分钟机器都在预热，一杯不出。第 $4$ 分钟结束时产出 $4$ 杯，还不到 $7$ 杯；第 $5$ 分钟结束时累计产出 $8$ 杯，首次不小于 $7$ 杯。此时上限 $8$ 杯才刚好被填满。