技能升级 ### 问题描述 小蓝最近正在玩一款 RPG 游戏。他的角色一共有 $N$ 个可以加攻击力的技能。 其中第 $i$ 个技能首次升级可以提升 $A_{i}$ 点攻击力, 以后每次升级增加的点数 都会减少 $\left.B_{i} 。 「 \frac{A_{i}}{B_{i}}\right\rceil$ (上取整) 次之后, 再升级该技能将不会改变攻击力。 现在小蓝可以总计升级 $M$ 次技能, 他可以任意选择升级的技能和次数。请 你计算小蓝最多可以提高多少点攻击力? ### 输入格式 输入第一行包含两个整数 $N$ 和 $M$ 。 以下 $N$ 行每行包含两个整数 $A_{i}$ 和 $B_{i}$ 。 ### 输出格式 输出一行包含一个整数表示答案。 ### 样例输入 ```txt 3 6 10 5 9 2 8 1 ``` ### 样例输出 ```text 47 ``` ### 评测用例规模与约定 对于 $40 \\%$ 的评测用例, $1 \leq N, M \leq 1000$; 对于 $60 \\%$ 的评测用例, $1 \leq N \leq 10^{4}, 1 \leq M \leq 10^{7}$; 对于所有评测用例, $1 \leq N \leq 10^{5}, 1 \leq M \leq 2 \times 10^{9}, 1 \leq A_{i}, B_{i} \leq 10^{6}$ 。