题解 | 来硬的

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10,INF=1e16; 

int n,m;
int xi[N],yi[N];
int dp[N][2];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;
	for(int i=0;i<=m;i++){
		dp[i][0]=INF;
		dp[i][1]=INF;
	}
	for(int i=1;i<=n;i++){
		cin>>xi[i]>>yi[i];
	}
	
	for(int i=1;i<=n;i++){
		for(int j=m;j>=0;j--){
			if(j<=xi[i]){
				dp[j][0]=min(dp[j][0],yi[i]);
			}
			if(j>xi[i]){
				dp[j][0]=min(dp[j][0],dp[j-xi[i]][0]+yi[i]);
				dp[j][1]=min(dp[j][1],dp[j-xi[i]][1]+yi[i]);
			}
			if(j<=2*xi[i]){
				dp[j][1]=min(dp[j][1],yi[i]/2);
			}
			if(j>2*xi[i]){
				dp[j][1]=min(dp[j][1],dp[j-2*xi[i]][0]+yi[i]/2);
			}
		}
	}
	
	cout<<dp[m][1]<<endl;
	
    return 0;
}