#include<bits/stdc++.h>
#define N 30010
using namespace std;
struct nood{int a , b;};
struct nod{int to,next,s;} edge[N * 100 * 6];
nood Start,End;
int s_long;
int n,m,b,p,heads[N],cnt=0;
bool pd[101][N];
bool PD[101][N];
int dist[101][N];
queue<pair<int,int>>  q;
vector<int> vis[N];
void add(int x,int y,int s){
	edge[++cnt].to = y;
	edge[cnt].next = heads[x];
	edge[cnt].s = s;
	heads[x] = cnt;
}
int main(){
	memset(dist,0x3f3f3f,sizeof(dist));
	cin >> n >> m ;
	s_long = sqrt(n / 3);
	s_long = min(s_long,100);
	if(s_long == 0) s_long = 1;
	for(int i=1;i<=m;i++){
		cin >> b >> p;
		b = b + 1;
		if(i == 1) Start.a = p, Start.b = b;
		if(i == 2) End.a = p, End.b = b;
		if(p == 0)	continue;
		if(p <= s_long && PD[p][b] == false){
			vis[b].push_back(p);
			PD[p][b] = true;
			continue;
		}
		if(p > s_long){
			int bs = 1;
			while(b + bs * p <= n){
				add(b , b + bs * p , bs);
				bs ++;
			}
			bs = -1;
			while(b + bs * p >= 1){
				add(b , b + bs * p , -bs);
				bs --;
			}
		}
	}
	q.push(make_pair(Start.a , Start.b));
	dist[Start.a][Start.b] = 0;
	while(q.size()){
		nood x;
		x.a = q.front().first , x.b = q.front().second;
		q.pop();
		//cout << x.a << "   " << x.b << "   " << dist[x.a][x.b] << endl;
		pd[x.a][x.b] = false;
		if(x.a == 0){
			for(int i=heads[x.b];i;i=edge[i].next){
				int s = edge[i].s;
				nood v;
				v.b = edge[i].to;
				v.a = 0;
				if(dist[v.a][v.b] > dist[x.a][x.b] + s){
					dist[v.a][v.b] = dist[x.a][x.b] + s;
					if(pd[v.a][v.b] == false){
						pd[v.a][v.b] = true;
						q.push(make_pair(v.a , v.b));
					}
				}
			}
			for(int i=0;i<vis[x.b].size();i++){
				int s = 0;
				nood v;
				v.a = vis[x.b][i];
				v.b = x.b;
				if(dist[v.a][v.b] > dist[x.a][x.b] + s){
					dist[v.a][v.b] = dist[x.a][x.b] + s;
					if(pd[v.a][v.b] == false){
						pd[v.a][v.b] = true;
						q.push(make_pair(v.a , v.b));
					}
				}
			}
		}
		else{
			nood v;
			v.a = 0, v.b = x.b;
			int s = 0;
			if(dist[v.a][v.b] > dist[x.a][x.b] + s){
				dist[v.a][v.b] = dist[x.a][x.b] + s;
				if(pd[v.a][v.b] == false){
					pd[v.a][v.b] = true;
					q.push(make_pair(v.a , v.b));
				}
			}
			
			v.a = x.a, v.b = x.b + x.a;
			s = 1;
			if(v.b <= n)if(dist[v.a][v.b] > dist[x.a][x.b] + s){
				dist[v.a][v.b] = dist[x.a][x.b] + s;
				if(pd[v.a][v.b] == false){
					pd[v.a][v.b] = true;
					q.push(make_pair(v.a , v.b));
				}
			}
			
			v.a = x.a, v.b = x.b - x.a;
			s = 1;
			if(v.b >= 1)if(dist[v.a][v.b] > dist[x.a][x.b] + s){
				dist[v.a][v.b] = dist[x.a][x.b] + s;
				if(pd[v.a][v.b] == false){
					pd[v.a][v.b] = true;
					q.push(make_pair(v.a , v.b));
				}
			}
		}
	}
	int ans = 999999999;
	int bs = 1;
	b = End.b;
	p = End.a;
	ans = min(ans , dist[0][b]);
	/*while(b + bs * p <= n){
		ans = min(dist[0][b + bs * p] + bs , ans);
		bs ++;
	}
	bs = -1;
	while(b + bs * p >= 1){
		ans = min(dist[0][b + bs * p] - bs , ans);
		bs --;
	}*/
	if(ans >=  999999999) cout << -1 << endl;
	else	cout << ans << endl;
	return 0;
}
/*
4 4
0 2
1 100
0 3
3 1

*/