#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using namespace std;
using pii=pair<int,int>;
struct Data{
int b,p,idx;
Data() {}
Data(int b,int p,int idx=0):b(b),p(p),idx(idx){}
bool operator<(const Data &rhs)const {
if(p!=rhs.p) return p<rhs.p;
else if(b%p!=rhs.b%rhs.p) return b%p < rhs.b%rhs.p;
else return b<rhs.b;
}
};
int n,m;
vector<Data> arr[30000];
int vis[10000001];
queue<pair<int, Data>> que;
void push(int cost,Data v) {
if(v.b-v.p>=0 && !vis[v.idx-1]) {
vis[v.idx-1]=1;
que.push({cost,Data(v.b-v.p,v.p,v.idx-1)});
}
if(v.b+v.p<n && !vis[v.idx+1]) {
vis[v.idx+1]=1;
que.push({cost,Data(v.b+v.p,v.p,v.idx+1)});
}
}
int main() {
int si,ei;
vector<Data> ta;
scanf("%d%d",&n,&m);
for(int i=0,a,b;i<m;i++) {
scanf("%d%d",&a,&b);
ta.push_back(Data(a,b));
if(i==0) si = a;
else if(i==1) ei = a;
}
sort(ta.begin(),ta.end());
for(int i=0,j=0,c=0;i<m;i=j) {
for(j=i;j<sz(ta) && ta[i].b%ta[i].p == ta[j].b%ta[j].p && ta[i].p == ta[j].p;j++);
for(int b=ta[i].b%ta[i].p, k=i;b<n;b+=ta[i].p,c++) {
while(k<j && b==ta[k].b) {
arr[b].push_back(Data(b,ta[i].p,c));
k++;
}
}
}
que.push({0, Data(si, 0, -1)});
while(!que.empty()) {
int cost=que.front().fi;
Data v=que.front().se;
que.pop();
if(v.b==ei) {
printf("%d\n",cost);
return 0;
}
if(v.p!=0) push(cost+1, v);
while(!arr[v.b].empty()) {
Data tmp=arr[v.b].back(); arr[v.b].pop_back();
push(cost+1, tmp);
}
}
puts("-1");
return 0;
}
