#include<bits/stdc++.h> using namespace std; int main(){ int m,k; cin>>m>>k; int dp[m+1],c[k],w[k]; for(int i=0;i<k;++i){ cin>>c[i]>>w[i]; } for(int i=0;i<m+1;++i)dp[i]=0; for(int i=0;i<k;++i){ for(int j=m;j>=c[i];--j) dp[j]=max(dp[j],dp[j-c[i]]+w[i]); } cout<<dp[m]<<endl; return 0; } |
Double click to view unformatted code.