题解：P12966 [CCO 2025] Asteroid Mining

#include<bits/stdc++.h>
using namespace std;
const int N=5e5 + 5;
#define int long long

int n,m,ans,b[N],tot,cnt,c[N];
struct node{
    int w,v;
}e[N];
bool cmp1(int s1,int s2){
    return s1>s2;
}
void solve(int x,int gx){
    cnt=(m%gx)/x;
    m-=cnt*x;
    sort(b+1,b+tot+1);
    for(int i=tot;i>=max(1ll,tot-cnt+1);--i){
        ans+=b[i];
    }
    tot=max(0ll,tot-cnt);
    if(!tot){
        return ;
    }
    int kk=gx/x;
    sort(b+1,b+tot+1,cmp1);
    for(int i=1;i<=tot;++i){
        c[i]=0;
    }
    for(int i=1;i<=tot;++i){
        c[(i-1)/kk+1]+=b[i];
    }
    tot=(tot-1)/kk+1;
    for(int i=1;i<=tot;++i){
        b[i]=c[i];
    }
}
bool cmp(node s1,node s2){
    if(s1.w==s2.w){
        return s1.v>s2.v;
    }
    return s1.w<s2.w;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>e[i].v>>e[i].w;
    }
    sort(e+1,e+n+1,cmp);
    int cur=e[1].w;
    for(int i=1;i<=n;++i){
        if(e[i].w!=cur){
            solve(cur,e[i].w);
            cur=e[i].w;
        }
        b[++tot]=e[i].v;
    }
    sort(b+1,b+tot+1);
    m/=e[n].w;
    for(int i=tot;i>=max(tot-m+1,1ll);--i){
        ans+=b[i];
    }
    cout<<ans<<'\n';
    return 0;
}