1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<algorithm> 6 #include<iomanip> 7 #include<cstdlib> 8 using namespace std; 9 const int maxn=101000;10 const int inf=100000000;11 int L,n;12 int w[maxn],v[maxn],c[maxn];13 void init(){14     scanf("%d%d",&L,&n);15     for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&v[i]);16 }17 void work(){18     memset(c,-10,sizeof(c));19     c[0]=inf;20     for(int i=1;i<=n;i++)21         for(int j=L;j>=0;j--){22             if(j<w[i])break;23             c[j]=max(c[j],min(c[j-w[i]],v[i]));24         }25     cout<<c[L]<<endl;26 }27 int main(){28     init();29     work();30 }