技能升级（2023寒假每日一题 13）

小蓝最近正在玩一款 RPG 游戏。

他的角色一共有 $N$ 个可以加攻击力的技能。

其中第 $i$ 个技能首次升级可以提升 $A_i$ 点攻击力，以后每次升级增加的点数都会减少 $B_i$。

$\lceil A_i/B_i\rceil$（上取整）次之后，再升级该技能将不会改变攻击力。
现在小蓝可以总计升级 $M$ 次技能，他可以任意选择升级的技能和次数。

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

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

以下 $N$ 行每行包含两个整数 $A_i$ 和 $B_i$。

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

数据范围
对于 $40\%$ 的评测用例，$1\le N,M\le 1000$；
对于 $60\%$ 的评测用例，$1\le N\le 10^4，1\le M\le 10^7$；
对于所有评测用例，$1\le N\le 10^5，1\le M\le 2\times 10^9，1\le A_i,B_i\le 10^6$。

输入样例：

3 6
10 5
9 2
8 1

输出样例：

47

---

#include<iostream>using namespace std;typedef long long LL;const int N = 100010;int n, m;
int a[N], b[N];bool check(int mid){LL res = 0;for(int i = 0; i < n; i++)if(a[i] >= mid)res += (a[i] - mid) / b[i] + 1;return res >= m;
}int main(){scanf("%d%d", &n, &m);for(int i = 0; i < n; i++) scanf("%d%d", &a[i], &b[i]);int l = 0, r = 1e6;while(l < r){int mid = l + r + 1 >> 1;if(check(mid)) l = mid;else r = mid - 1;}LL res = 0, cnt = 0;for(int i = 0; i < n; i++)if(a[i] >= r){int c = (a[i] - r) / b[i] + 1;int end = a[i] - (c - 1) * b[i];cnt += c;res += (LL)(a[i] + end) * c / 2;}printf("%lld\n", res - (cnt - m) * r);return 0;
}