> #include <cstdio>
> #include <cstring>
> #define Max(a,b) (a)>(b)?(a):(b)
> 
> int dp[100001],Cost[11],Count[11],cash;
> 
> void ZeroOnePack(int cost){
> 	int i;
> 	for(i=cash;i>=cost;i--)
> 	    dp[i]=Max(dp[i],dp[i-cost]+cost);
> }
> 
> void CompletePack(int cost){
> 	int i;
> 	for(i=cost;i<=cash;i++)
> 	    dp[i]=Max(dp[i],dp[i-cost]+cost);
> }
> 
> void MultiplePack(int cost,int count){
> 	if(cost*count > cash)
> 	    CompletePack(cost);
> 	else{
> 		int k=1;
> 		while(k < count){
> 			ZeroOnePack(k*cost);
> 			count -= k;
> 			k *= 2;
> 		}
> 		ZeroOnePack(count*cost);
> 	}
> }
> 
> 
> int main(){
> 	int n,i,j,k;
> 	while(~scanf("%d%d",&cash,&n)){
> 		for(i=1;i<=n;i++)
> 			scanf("%d%d",&Count[i],&Cost[i]);			
> 		memset(dp,0,sizeof(dp));
> 		for(i=1;i<=n;i++)
> 			MultiplePack(Cost[i],Count[i]);
> 		printf("%d\n",dp[cash]);
> 	}
> 	return 0;
> }