> #include <stdio.h>
> #define mun(a, b) ((a) > (b) ? (a) : (b))
> int result[100005];
> int cash, n;
> 
> void ZeroOnePack(int cost)		//01背包问题的一维数组优化, 逆序求解
> {
> 	int i;
> 	for(i = cash; i >= cost; i--)
> 		result[i] = mun(result[i], result[i - cost] + cost);
> }
> 
> void CompletePack(int cost)		//完全背包问题，正序求解
> {
> 	int i;
> 	for(i = cost; i <= cash; i++)
> 		result[i] = mun(result[i], result[i - cost] + cost);
> }
> 
> void MultiPack(int cost, int amount)		//多重背包问题转换成01背包问题
> {
> 	if(cost * amount >= cash)		//单一物件超出最大值则转换成完全背包
> 	{
> 		CompletePack(cost);
> 		return;
> 	}
> 	int k = 1;
> 	while(k < amount)
> 	{
> 		ZeroOnePack(cost*k);
> 		amount -= k;
> 		k *= 2;
> 	}
> 	ZeroOnePack(cost*amount);
> }
> 
> int main()
> {
> 	int i;
> 	int n1[12], dk[12];
> 	while(scanf("%d%d", &cash, &n) != EOF)
> 	{
> 		for(i = 1; i <= n; i++)
> 			scanf("%d%d", &n1[i], &dk[i]);
> 		if(n == 0 || cash == 0)
> 		{
> 			cash = 0;
> 			printf("%d\n", cash);
> 			continue;
> 		}
> 		for(i = 0; i <= n; i++)		//初始化
> 			result[i] = 0;
> 		for(i = 1; i <= n; i++)
> 			MultiPack(dk[i], n1[i]);
> 		printf("%d\n", result[cash]);
> 	}
> 	return 0;
> }