好题我懂得欣赏。

首先给所有物品按照重量排序，显然只有 $\log V$ 种不同的重量。

然后考虑最轻的物品，假设重量为 $w$，显然可以 $m \gets \frac{m}{w}$ 然后给所有物品重量除一个 $w$。

这个时候先把目前重量为 $1$ 的物品排序，然后设这个时候次轻的物品重量为 $w_1$。

我们考察最后的方案中，重量为 $1$ 的物品所占的背包重量，一定可以等效地看作 $m \bmod w_1 + k \times w_1$，这是因为其余的物品重量都是 $w_1$ 的倍数，所以其余的物品所占重量一定形如 $l \times w_1$，故有此结论。

那么我们考虑将重量为 $1$ 的物品先选前 $m \bmod w_1$ 大直接加入答案，然后将剩下的排序后每 $w_1$ 个合并为 $1$ 个重量为 $w_1$ 的物品（最后一组可能不够 $w_1$ 个但是视作重量为 $w_1$ 是没有影响的），此时 $w_1$ 变为最轻的重量，重复上述过程即可。

一共 $\log V$ 层，瓶颈在每层的排序，注意到每往后一层物品数量至少减半，故一个物品对每层的大小贡献是 $O(\sum_{i=0}^{\log V} \frac{1}{2^i}) = O(1)$ 的，总时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
const int maxn = 5e5+114;
pair<int,int> a[maxn];
int ans;
vector<int> dp;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].second;
        cin>>a[i].first;
    }
    sort(a+1,a+n+1);
    m/=a[1].first;
    int now=a[1].first;
    for(int i=1;i<=n;i++){
        if(a[i].first==now){
            dp.push_back(a[i].second);
        }else{
            sort(dp.begin(),dp.end());
            int M=m%(a[i].first/a[i-1].first);
            while(M>0&&dp.size()>0) ans+=dp.back(),dp.pop_back(),M--;
            m/=(a[i].first/a[i-1].first);
            int c=a[i].first/a[i-1].first;
            vector<int> f;
            while(dp.size()>0){
                int s=0;
                for(int j=1;j<=c&&dp.size()>0;j++) s+=dp.back(),dp.pop_back();
                f.push_back(s);
            }
            swap(f,dp);
            dp.push_back(a[i].second);
            now=a[i].first;
        }
    }
    sort(dp.begin(),dp.end());
    while(m>0&&dp.size()>0) ans+=dp.back(),m--,dp.pop_back();
    cout<<ans<<"\n";
    return 0;
}