View Code of Problem 611

# include <stdio.h>
  int main()
  {
	  int i,j,t,m,n,k,c,dp[1005];
	  while(scanf("%d%d",&m,&n)!=EOF)
	  {
		  for(i=1;i<=1005;i++)
			  dp[i]=999999;
		  dp[0]=0;
		  for(i=0;i<n;i++)
		  {
			  scanf("%d%d",&k,&c);
			  for(t=m;t>=1;t--)
				  for(j=1;j<=c;j++)
					  if(t-j*k>=0&&dp[t-j*k]+j<dp[t])
						  dp[t]=dp[t-j*k]+j;
		  }
		  if(dp[m]==999999)
			  printf("Naivete\n");
		  else
			  printf("%d\n",dp[m]);
	  }
	  return 0;
  }