2047: [蓝桥杯2022初赛] 技能升级

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:276 通过:63

题目描述

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