#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;
multiset <int>  s;
struct node{
	int x,y;
};
node an[20];
int n,m;
bool cmp(node a,node b)
{
	return a.x>b.x;
}
int main()
{
	freopen("HanXin.in","r",stdin);
	freopen("HanXin.out","w",stdout);
	int mixx=(1<<29);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&an[i].x,&an[i].y);
		mixx=min(an[i].x,mixx);
	}
	sort(an+1,an+1+m,cmp);
	int bj=n/mixx+1;
	for(int i=bj;i>=0;i--)
	{
		for(int j=1;j<=m;j++)
		{
			int k=an[j].x*i+an[j].y;
			s.insert(k);
			if(s.count(k)==3)
			{
				printf("%d\n",n-k);
				return 0;
			}
		}
	}
	printf("-1\n");
	return 0;
}