> #include <iostream>
> 
> int cash;            
> int N;                 //货币种数
> int num[11];           //每种货币数量数组
> int value[11];         //每种货币价值
> int f[100001];         //动态规划数组
> #define Max(a,b) (a)>(b)?(a):(b)
> 
> void ZeroOnePack(int cost, int weight)
> {
> 	for (int i = cash; i >= cost; i--)
> 	{
> 		f[i] = Max(f[i], f[i - cost] + weight);
> 	}
> }
> 
> void CompletePack(int cost, int weight)
> {
> 	for (int i = cost; i <= cash; i++)
> 	{
> 		f[i] = Max(f[i], f[i - cost] + weight);
> 	}
> }
> 
> int main(void)
> {
> 	while (std::cin >> cash >> N)
> 	{
> 		for (int i = 0; i < N; i++)
> 		{
> 			std::cin >> num[i];
> 			std::cin >> value[i];
> 		}
> 		memset(f, 0, sizeof(f));
> 		for (int i = 0; i < N; i++)
> 		{
> 			if (num[i] * value[i] > cash)
> 			{
> 				CompletePack(value[i], value[i]);
> 			}
> 			else
> 			{
> 				int k = 1;
> 				int amount = num[i];
> 				while (k < amount)
> 				{
> 					ZeroOnePack(value[i], value[i]);
> 					amount -= k;
> 					k *= 2;
> 				}
> 				ZeroOnePack(amount * value[i], amount * value[i]);
> 			}
> 		}
> 		std::cout << f[cash] << std::endl;
> 	}
> 	return 0;
> }