问题描述

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

其中第 $i$ 个技能首次升级可以提升 $A_{i}$ 点攻击力, 以后每次升级增加的点数都会减少 $B_i$ 。 $\lceil \frac{A_i}{B_i}\rceil$ (上取整) 次之后, 再升级该技能将不会改变攻击力。

现在小蓝可以总计升级 $M$ 次技能, 他可以任意选择升级的技能和次数。请你计算小蓝最多可以提高多少点攻击力?

输入格式

输入第一行包含两个整数 $N$ 和 $M$ 。

以下 $N$ 行每行包含两个整数 $A_{i}$ 和 $B_{i}$ 。

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

对于 40% 的评测用例, $1≤N,M≤1000$ ;

对于 60% 的评测用例, $1≤N≤10^4, 1≤M≤10^7$ ;

对于所有评测用例, $1≤N≤10^5, 1≤M≤2×10^9, 1≤A_i, B_i≤10^6$ 。