View Code of Problem 4056

#include<iostream>
#include<string.h>
using namespace std;
int main(){
	int W,K;
	while(cin>>W>>K){
		int ar[K],V[K],dp[W+1];
		memset(dp,0,sizeof(dp)); 
		for(int i=0;i<K;i++){
			cin>>ar[i]>>V[i];
		}
		for(int i=0;i<K;i++){
			for(int j=W;j>=ar[i];j--){
				dp[j]=max(dp[j],dp[j-ar[i]]+V[i]);
			}
		}
		cout<<dp[W]<<endl;
	}
}