90PTS 求调

#include<bits/stdc++.h>
#define int long long
#define cnm n=rd(),W=rd()
using namespace std;
const int N=1e6+5;
int n,W,v,w,ma,mi=3141592653,ans,f[N];
pair<int,int> g[N],o;
inline int rd(){
	int s=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
signed main(){
	cnm;
	for(int i=1;i<=n;++i){
		v=rd();w=rd();
		g[i]={w,v};
		mi=min(mi,v);
		ma=max(ma,v);
	}
	if(mi<=n*3){
		W=min(W,ma*3);
		for(int j=1;j<=n;++j)
		    for(int i=W;i>=g[j].second;--i)
		        f[i]=max(f[i],f[i-g[j].second]+g[j].first);
		cout<<f[W];
	}
	else{
		sort(g+1,g+n+1);
		for(int i=n;i;i--){
			W-=g[i].second;
			if(W>=0) ans+=g[i].first;
			else W+=g[i].second;
		}
		cout<<ans;
	}
	return 0;
}