技能升级

本题总分：25 分

【问题描述】

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

能。其中第 i 个技能首次升级可以提升 Ai 点攻击力，以后每次升级增加的点数

都会减少 Bi。⌈ Ai Bi⌉ (上取整) 次之后，再升级该技能将不会改变攻击力。

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

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

【输入格式】

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

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

【输出格式】

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

【样例输入】

3 6

10 5

9 2

8 1

【样例输出】

47