View Code of Problem 4045

#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;
}