小蓝最近正在玩一款 RPG 游戏。他的角色一共有 N 个可以加攻击力的技能。其中第 i 个技能首次升级可以提升 Ai 点攻击力，以后每次升级增加的点数都会减少 Bi。

(上取整) 次之后，再升级该技能将不会改变攻击力。 

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

输入格式

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

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

输出格式

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

样例输入

3 6
10 5
9 2
8 1

样例输出

47

提示

对于 40% 的评测用例，1 ≤ N, M ≤ 1000；

对于 60% 的评测用例，1 ≤ N ≤ 1e4 , 1 ≤ M ≤ 1e7；

对于所有评测用例，1 ≤ N ≤ 1e5，1 ≤ M ≤ 2 × 1e9，1 ≤ Ai , Bi ≤ 1e6。 

初看时觉得听简单，搞个大根堆取个m次，但要注意，这样写显然要超时了，这道题正确思路是二分答案，但是这个二分答案还不一般，二分的并非是攻击力，（因为这样写你的check函数也是超时的）而是要找到一个阈值，使得大于它的收益数量大于等于m，且使得该阈值最大，这样写确实不会超时了wc，因为时间复杂度跟m无关了

“我们费劲二分出来这个 x，到底拿来干嘛？”

很多人卡的就是这里。

---

🎯 一句话答案

x = 第 m 大的值（阈值）

👉 它的作用是：

🔥 把“选前 m 大”变成“分段求和”

---

🧠 你原问题是什么？

从所有数里选最大的 m 个

👉 但问题是：

数太多，不能一个个取 ❌

---

🚀 引入 x 的作用

我们找一个数 x，使得：

≥ x 的数有至少 m 个

---

🔥 关键变化

有了 x 之后：

所有数被分成三类：

---

① > x 的（必须全选）

这些肯定在前 m 大里 ✅

---

② = x 的（可能选一部分）

可能多了，需要裁掉一部分 ⚠️

---

③ < x 的（一个都不要）

肯定不在前 m 大 ❌

---

🧠 所以你现在能干嘛？

👉 你可以：

✔ 一次性算出所有 ≥ x 的总和

不用一个个取！

---

🧮 但是问题来了

≥ x 的数量 = cnt ≥ m

👉 可能多选了！

---

🔥 解决办法

total -= (cnt - m) * x;

---

🧠 这句的含义

👉 多选的那些数：

全部都是 x（最小的那一档）

👉 所以直接减掉：

(cnt - m) 个 x

以下附上代码：

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int maxn = 100005;

ll n, m;

ll a[maxn], b[maxn];

bool check(ll x){

    ll cnt = 0;

    for(int i = 1; i <= n; i++){

        if(a[i] < x) continue;

        cnt += (a[i] - x) / b[i] + 1;

        if(cnt >= m) return true;

    }

    return false;

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cin >> n >> m;

    ll r = 0;

    for(int i = 1; i <= n; i++){

        cin >> a[i] >> b[i];

        r = max(r, a[i]);

    }

    ll l = 0, ans = 0;

    while(l <= r){

        ll mid = (l + r) >> 1;

        if(check(mid)){

            ans = mid;

            l = mid + 1;

        }else{

            r = mid - 1;

        }

    }

    // 计算答案

    ll total = 0, cnt = 0;

    for(int i = 1; i <= n; i++){

        if(a[i] < ans) continue;

        ll k = (a[i] - ans) / b[i] + 1;

        cnt += k;

        ll last = a[i] - (k - 1) * b[i];

        total += (a[i] + last) * k / 2;

    }

    total -= (cnt - m) * ans;

    cout << total << "\n";

}