技能升级（2023寒假每日一题 13）
小蓝最近正在玩一款 RPG 游戏。
他的角色一共有 N N N 个可以加攻击力的技能。
其中第 i i i 个技能首次升级可以提升 A i A_i Ai 点攻击力，以后每次升级增加的点数都会减少 B i B_i Bi。
⌈ A i / B i ⌉ ⌈A_i/B_i⌉ ⌈Ai/Bi⌉（上取整）次之后，再升级该技能将不会改变攻击力。
现在小蓝可以总计升级 M M M 次技能，他可以任意选择升级的技能和次数。
请你计算小蓝最多可以提高多少点攻击力？
输入格式
输入第一行包含两个整数 N N N 和 M M M。
以下 N N N 行每行包含两个整数 A i A_i Ai 和 B i B_i Bi。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 40 % 40\% 40% 的评测用例， 1 ≤ N , M ≤ 1000 1≤N,M≤1000 1≤N,M≤1000；
对于 60 % 60\% 60% 的评测用例， 1 ≤ N ≤ 1 0 4 ， 1 ≤ M ≤ 1 0 7 1≤N≤10^4，1≤M≤10^7 1≤N≤104，1≤M≤107；
对于所有评测用例， 1 ≤ N ≤ 1 0 5 ， 1 ≤ M ≤ 2 × 1 0 9 ， 1 ≤ A i , B i ≤ 1 0 6 1≤N≤10^5，1≤M≤2×10^9，1≤A_i,B_i≤10^6 1≤N≤105，1≤M≤2×109，1≤Ai,Bi≤106。
输入样例：
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;
}