P12370 [蓝桥杯 2022 省 Python B] 技能升级

小蓝最近正在玩一款 RPG 游戏。他的角色一共有 $N$ 个可以加攻击力的技能。其中第 $i$ 个技能首次升级可以提升 $A_i$ 点攻击力，以后每次升级增加的点数都会减少 $B_i$。$\lceil\frac{A_i}{B_i}\rceil$（上取整）次之后，再升级该技能将不会改变攻击力。 现在小蓝可以总计升级 $M$ 次技能，他可以任意选择升级的技能和次数。请你计算小蓝最多可以提高多少点攻击力？

输入第一行包含两个整数 $N$ 和 $M$。 以下 $N$ 行每行包含两个整数 $A_i$ 和 $B_i$。

输出一行包含一个整数表示答案。

### 评测用例规模与约定 - 对于 $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$。