小蓝最近正在玩一款 RPG 游戏。他的角色一共有 N 个可以加攻击力的技能。其中第 i 个技能首次升级可以提升 A_i 点攻击力，以后每次升级增加的点数都会减少 B_i。(上取整) 次之后，再升级该技能将不会改变攻击力。 

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

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

以下 N 行每行包含两个整数 A_i 和 B_i。

3 6
10 5
9 2
8 1

47

对于 40% 的评测用例，1 ≤ N, M ≤ 1000；

对于 60% 的评测用例，1 ≤ N ≤ 10⁴ , 1 ≤ M ≤ 10⁷；

对于所有评测用例，1 ≤ N ≤ 10⁵，1 ≤ M ≤ 2 × 10⁹，1 ≤ A_i , B_i ≤ 10⁶。