题目内容

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

其中第 $1$ 个技能首次升级可以提升 $Ai$ 点攻击力，以后每次升级增加的点数都会减少 $B_i$ 。$\lceil Ai/Bi \rceil$ (上取整) 次之后，再升级该技能将不会改变攻击力。

现在小蓝可以总计升级 $M$ 次技能，他可以任意选择升级的技能和次数。

请你计算小蓝最多可以提高多少点攻击力?

输入描述

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

以下 $N$ 行每行包含两个整数 $Ai$ 和 $Bi$ 。

输出描述

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

样例1

输入

3 6
10 5
9 2
8 1

输出

47