方法一：树状数组:O(nlogn)

/*
    先枚举组团，后分析每个士兵，有一个特点，组团费用是固定的，那当然是让所有士兵一块训练，训练完的士兵也不会有损失
    当还需要升级的士兵的金币之和小于组团时就各自训练，此时花费也已经固定了
    首先将经验按照从大到小排序，这样每次组团训练，会从后向前减少不需要训练的士兵，这样就能利用前缀和来判断是否需要单独训练
    每次组团先训练完一整类需要经验值相同的士兵再判断, 由于会对一整个区间进行修改求和，使用树状数组
    时间复杂度O(n)
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long

using namespace std;

const int N = 100010;

struct Soldier{
    int coin, ep;
    bool operator< (const Soldier o) const{
        return ep > o.ep;
    }
}sl[N];

int sc[N], tr[N];
int n, S;

int lowbit(int x){
    return x & -x;
}

void add(int x, int c){
    for (int i = x; i < N; i += lowbit(i))
        tr[i] += c;
}

int sum(int x){
    int s = 0;
    for (int i = x; i; i -= lowbit(i))
        s += tr[i];
    return s;
}

signed main(){
    scanf("%lld%lld", &n, &S);

    for (int i = 1; i <= n; i ++){
        scanf("%lld%lld", &sl[i].coin, &sl[i].ep);
    }
    sort(sl + 1, sl + n + 1);

    for (int i = 1; i <= n; i ++){
        sc[i] = sc[i - 1] + sl[i].coin;
        add(i, sl[i].ep - sl[i - 1].ep);
    }

    int res = 0;
    for (int i = n; i; i --){
        int cep = sum(i);
        if (cep > 0){
            if (sc[i] >= S){
                add(1, -cep);
                add(i, cep);
                res += S * cep;
            }
            else{
                res += sl[i].coin * cep;
            } 
        }
    }

    printf("%lld\n", res);

    return 0;
}

方法二：哈希+整体操作: O(n)

换个角度更简单

/*
    由于组团训练肯定是所有士兵一起参加更好，
    所以可以把过程分为两种情况，一种是所有士兵组团训练，一种是所有士兵单独训练，而哪些已经训练完成的士兵就不用管了
    每次比较是组团和单独训练的花费金额来判断选用哪种情况
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long

using namespace std;

const int N = 100010;

int c[N], p[N];
int n, S;
int a[N * 100]; // a[k]哈希表，表示经过k轮后，完成训练后对应士兵的花费

signed main(){
    scanf("%lld%lld", &n, &S);

    int maxt = 0;//一共只需要升maxt次所有士兵就能升满级
    int i_S = 0;//表示单独训练花费
    for (int i = 1; i <= n; i ++){
        scanf("%lld%lld", &c[i], &p[i]);
        maxt = max(maxt, p[i]);
        i_S += c[i];
        a[p[i]] += c[i];//训练多少轮后到达满级，此时对应的i_s将其去掉，未到满级是a[i]为0
    }

    int res = 0;
    for (int i = 1; i <= maxt; i ++){
        if (S < i_S){
            res += S;
        }
        else{
            res += i_S;
        }
        i_S -= a[i];
    }

    printf("%lld\n", res);
    return 0;
}