View Code of Problem 4045

#include <stdio.h>
int n,c;
int dp[100010]={0};
int max(int a,int b)
{
	return a<b?b:a;
}


int getvalue(int kg,int value)
{
	for(int i=c;i>=kg;i--)
	{
		dp[i]=max(dp[i],dp[i-kg]+value);
	}
}




int main()
{
	
	int val[10010]={0};
	int weight[10010]={0};
	scanf("%d%d",&c,&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d%d",&weight[i],&val[i]); 
	}
	for(int i=0;i<n;i++)
	{
		getvalue(weight[i],val[i]);
	}
	printf("%d\n",dp[c]);
}