/*多重背包问题，本题如不使用二进制分物品可能会超时，
毕竟数目不小。另一个要注意的点是不用考虑找的最少钱数，
只要能找出钱就行了，因此用0和1（dp[0]=1)赋值就行了，如
果能找到钱就赋非0值，结果输出dp值为非0的最大数就行了。*/
#include <cstdio>

int value[100];

int dp[100010];
int main()
{
	int cash,n,count,num,val;
	while(scanf("%d",&cash)!=EOF)
	{
        count=0;	
		scanf("%d",&n);
		for ( int i=0;i<n;i++)
		{
             scanf("%d%d",&num,&val);
			 int k=1;
			 while (num-k>=0)
			 {
				 num-=k;
				 value[count++]=k*val;
				 k*=2;
			 }
			 if (num) value[count++]=num*val;
			
		}
				 

		for (int i=1;i<=cash;i++)
			dp[i]=0;
		dp[0]=1;
       
		for (int i=0;i<count;i++)
				for (int v=cash;v>=value[i];v--)
					if (!dp[v])
						dp[v]=dp[v-value[i]];
					

		for (int i=cash;i>=0;i--)
			if (dp[i])
			{ printf("%d\n",i); break;}
	}

		return 0;
}