思路

要在 $N$ 条“收益递减”序列中选取总共 $M$ 次升级，使得总收益最大。对于第 $i$ 个技能，它的每次升级收益依次为：

$A_i,A_i - B_i,A_i - 2B_i,\dots,A_i - (k-1)B_i,$

其中最多 $k_{\max} = \lceil \frac{A_i}{B_i}\rceil$ 次，且当 $A_i - (k-1)B_i \le 0$ 时就不再产生收益。

直接按「每次都选当前最大收益」的贪心（用优先队列）在 $M$ 较大时会超时。更高效的方法是二分阈值 $T$，对每个技能计算“有多少次升级的收益 $\ge T$”，记为

题目内容

小蓝最近正在玩一款 RPG 游戏。他的角色一共有 $N$ 个可以加攻击力的技能。

其中第 $1$ 个技能首次升级可以提升 $Ai$ 点攻击力，以后每次升级增加的点数都会减少 $B_i$ 。$\lceil Ai/Bi \rceil$ (上取整) 次之后，再升级该技能将不会改变攻击力。