View Code of Problem 611

#include<stdio.h>
#include<string.h>
#define min(a,b) (((a) < (b)) ? (a) : (b))
int max(int i,int j)
{
	if(i>j)
		return i;
	return j;
}
int main()
{
	int i,j,n,m,k,c,t,v[1200];
	int temp[120];
	while(scanf("%d%d",&m,&n)!=EOF)
	{
		v[0]=0;
		for(i=1;i<=m;i++)
			v[i]=10000;
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&k,&c);
			for(j=0;j<c;j++)
				for (t = m; t >= 0; --t) 
				{
					if(t-k>=0)
					{
						if(v[t-k]!=10000)
							v[t]=min(v[t],v[t-k]+1);
					}
				}
		}
		if(v[m]==10000)
			printf("Naivete\n");
		else 
			printf("%d\n",v[m]);
	}
	return 0;
}