z1366.cpp

zoj solved 今年在zoj上a的题目

//zju1366 Cash Machine 07.10.04
#include <stdio.h>
#include <string.h>

int cash,n;
int nk[1000],dk[1000];
bool st[100001];

int solve();

int main()
{
	int i;
	int rslt;
	while(scanf("%d%d",&cash,&n) == 2)
	{
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&nk[i],&dk[i]);
		}
		rslt = solve();
		printf("%d\n",rslt);
	}

	return 0;
}

int solve()
{
	if(cash==0 || n==0) return 0;
	int i,j,k,t;
	memset(st,0,sizeof(st));
	st[0] = 1;
	for(i=0;i<n;i++)
	{
		for(j=cash-1;j>=0;j--)
		{
			if(st[j] == 1)
			{
				for(k=1;k<=nk[i];k++)
				{
					t = j + k*dk[i];
					if(t > cash) break;
					else if(t == cash) return cash;
					else st[t] = 1;
				}
			}
		}
	}
	for(i = cash -1;i>=0;i--)
	{
		if(st[i] == 1) return i;
	}
	return 0;
}