#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
int n,target,id,a[30010];
bool f[100010];

void init()
{
	memset(f,0,sizeof(f));
	f[0]=1;id=0;
	int x,y,k,t;
	for(int i=1;i<=n;i++)
		{
			scanf("%d%d",&x,&y);
			if(!(x&&y)) continue;
			k=min(y,target/x);
			t=1;
			while(t<=k)
			{
				id++;a[id]=t*x;
				if(a[id]>target) id--;
				t<<=1;
			}
			t>>=1;
			if(t<k)
			{
				id++;a[id]=(k-t)*x;
				if(a[id]>target) id--;
			}
		}
}

int main()
{
	//freopen("sss.in","r",stdin);
	//freopen("sss.out","w",stdout);
	while(scanf("%d%d",&target,&n)!=EOF)
	{
	    init();
		if(!(target&&n))
		{
			cout<<0<<endl;
			continue;
		}
		for(int i=1;i<=id;i++)
		    for(int j=target;j>=a[i];j--)
		        if(f[j-a[i]])
		            f[j]=1;
		while(f[target]!=1&&target>0) target--;
		cout<<target<<endl;
	}
	return 0;
}