题目描述

小蓝最近正在玩一款 $RPG$ 游戏。

他的角色一共有 $N$ 个可以加攻击力的技能。

其中第 $i$ 个技能首次升级可以提升 $A_i$ 点攻击力，以后每次升级增加的点数都会减少 $B_i$。

$\left\lceil \frac{A_i}{B_i} \right\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。$

输入样例：

3 6
10 5
9 2
8 1

输出样例：

47

题目来源：

第十三届蓝桥杯省赛 $C++ C$ 组。

第十三届蓝桥杯省赛 $Java$ 研究生组。

第十三届蓝桥杯省赛 $Python B$ 组，研究生组。