//#include<bits/stdc++.h> //using namespace std; //int max(int a,int b,int c){ // return max(max(a,b),c); //} //int main(){ // int m,n,a[205],b[205],dp[35][205];//取前n个物品，背包容量为m的最大价值 // memset(dp,0,sizeof(dp)); // cin>>m>>n; // for(int i=1;i<=n;i++){ // cin>>a[i]>>b[i]; // } // for(int j=1;j<=m;j++){ // for(int i=1;i<=n;i++){ // dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]]+b[i],dp[i][j]); // } // } // cout<<dp[n][m]; // return 0; //} #include<bits/stdc++.h> using namespace std; int main(){ int n,m,a[205],b[205],dp[205];//第i项表示容量为i时最值 memset(dp,0,sizeof(dp)); cin>>m>>n; for(int i=1;i<=n;i++){ cin>>a[i]>>b[i]; } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ if(i-a[j]>=0) dp[i]=max(dp[i-1],dp[i-a[j]]+b[j]); else dp[i]=dp[i-1]; } } cout<<"max="<<dp[m]; return 0; }