题目描述

小蓝最近正在玩一款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。

输出格式

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

输入样例

3 6
10 5
9 2
8 1

输出样例

47