题解

#include<bits/stdc++.h>
using namespace std;
long long a[100005],b[100005],n,m,dp[100005],cnt=1e9,sum=1e9;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
for(int i=1;i<=n;i++){
for(int j=b[i];j>=a[i];j--){
dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
}
}
for(int i=1;i<=m;i++){
if(dp[i]>=m){
cnt=min(cnt,dp[i]);
}
}
if(cnt==1e9){
cout<<"no solution";
}else{
for(int i=1;i<=n;i++){
for(long long j=b[i];j>=a[i];j--){
if(dp[j]==cnt){
sum=min(sum,j);
}
}
}
cout<<sum;
}
}//其实这题可以用普通01背包思想，遍历求最小值，简单易懂。