j06623. 冲刺·薪资预算 未做

机房里有 $n$ 台服务器排成一排，第 $i$ 台服务器的基础算力为 $a_i$。

运维手里有一笔电力配额：每给第 $i$ 台服务器投入 $c_i$ 单位电力，它的算力就增加 $b_i$。若总共投入 $x$ 单位电力（$x$ 为整数），则第 $i$ 台服务器的最终算力为

即每凑满 $c_i$ 单位电力，第 $i$ 台就涨 $b_i$ 点算力，不足 $c_i$ 的零头不起作用。

电力从两个方向受限：算力总预算为 $T$（$n$ 台服务器最终算力之和不得超过 $T$），电力配额上限为 $X$（$0\le x\le X$）。

请求出满足总算力不超过 $T$ 的最大非负整数 $x$。

数据保证 $x=0$ 时总算力不超过预算（即 $\sum a_i\le T$）。

第一行三个整数 $n,T,X$。

接下来 $n$ 行，每行三个整数 $a_i,b_i,c_i$。

输出一个整数，表示最大的电力投入量 $x$。

【样例解释】

• 样例 1：当 $x=3$ 时，三台服务器算力分别为 $1+2\times \lfloor 3/1\rfloor =7$、$2+3\times \lfloor 3/2\rfloor =5$、$3+1\times \lfloor 3/1\rfloor =6$，总和 $7+5+6=18\le 20$；当 $x=4$ 时总和为 $9+8+7=24>20$。故答案为 $3$。
• 样例 2：两台服务器的 $b_i$ 均为 $0$，投入多少电力算力都不变，总和恒为 $10\le 10$，所以答案取到上界 $X=100$。

【数据范围】

对于全部数据，满足 $1\le n\le 2\times 10^5$，$0\le a_i,b_i\le 10^9$，$1\le c_i\le 10^9$，$1\le T\le 10^9$，$0\le X\le 10^9$，且保证 $\sum a_i\le T$。

共 20 个测试点，每个测试点 5 分，合计 100 分。