内存限制：256 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：771
通过：133
小蓝最近正在玩一款RPG 游戏。他的角色一共有N个可以加攻击力的技能。
其中第i个技能首次升级可以提升Ai点攻击力，以后每次升级增加的点数都会减少Bi。
⌈Ai/Bi⌉ (向上取整) 次之后，再升级该技能将不会改变攻击力。
现在小蓝可以总计升级M次技能，他可以任意选择升级的技能和次数。
请你计算小蓝最多可以提高多少点攻击力？
输入第一行包含两个整数N和M。
以下N行每行包含两个整数Ai和Bi。
对于40% 的评测用例，1 ≤ N, M ≤ 1000；
对于60% 的评测用例，1 ≤ N ≤ 10^4; 1 ≤ M ≤ 10^7；
对于所有评测用例，1 ≤ N ≤ 10^5，1 ≤ M ≤ 2 × 10^9，1 ≤ Ai; Bi ≤ 10^6。