#P12370. [蓝桥杯 2022 省 Python B] 技能升级

[蓝桥杯 2022 省 Python B] 技能升级

题目描述

小蓝最近正在玩一款 RPG 游戏。他的角色一共有 NN 个可以加攻击力的技能。其中第 ii 个技能首次升级可以提升 AiA_i 点攻击力,以后每次升级增加的点数都会减少 BiB_iAiBi\lceil\frac{A_i}{B_i}\rceil(上取整)次之后,再升级该技能将不会改变攻击力。

现在小蓝可以总计升级 MM 次技能,他可以任意选择升级的技能和次数。请你计算小蓝最多可以提高多少点攻击力?

输入格式

输入第一行包含两个整数 NNMM

以下 NN 行每行包含两个整数 AiA_iBiB_i

输出格式

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

3 6
10 5
9 2
8 1
47

提示

评测用例规模与约定

  • 对于 40%40\% 的评测用例, 1N,M10001 \leq N, M \leq 1000;
  • 对于 60%60\% 的评测用例, 1N1041 \leq N \leq 10^4, 1M1071 \leq M \leq 10^7;
  • 对于所有评测用例, 1N1051 \leq N \leq 10^5, 1M2×1091 \leq M \leq 2 \times 10^9, 1Ai,Bi1061 \leq A_i, B_i \leq 10^6