> #include<cstdio>
> #include<cstring>
> #include<algorithm>
> using namespace std;
> int W,n;
> int w[10005];
> int cnt;
> int dp[100005];
> int main()
> {
> 	while(scanf("%d%d",&W,&n)!=EOF)
> 	{
> 		memset(dp,0,sizeof(dp));
> 		cnt=0;
> 		for(int i=0;i<n;i++)
> 		{
> 			int b,v;
> 			scanf("%d%d",&b,&v);
> 			int e=1;
> 			while(e<=b)
> 			{
> 				w[cnt++]=e*v;
> 				b-=e;
> 				e<<=1;	
> 			}
> 			w[cnt++]=b*v;
> 		}
> 		
> 		for(int i=0;i<cnt;i++)
> 			for(int j=W;j>=w[i];j--)
> 				dp[j]=max(dp[j],dp[j-w[i]]+w[i]);
> 		
> 		printf("%d\n",dp[W]);
> 	}
> 	
> 	return 0;
> }