#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,vector<int>>mp;
vector<int> up[10000005];
int down1[10000005],down2[10000005],hor[10000005];
vector<int>dis;
int inf=1e9;
int have[15000005];
deque<pair<int,int>>dq;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,m;cin>>n>>m;
if(n>3e4)for(int i=0;i<n;i);
//assert(n<=3e4);
int st=0,en=0;
for(int i=0;i<m;i++){
int b,p;cin>>b>>p;
if(i==0)st=b;
if(i==1)en=b;
if(i!=1)mp[{b%p,p}].push_back(b);
have[b]++;
}
int id=n-1;
for(int i=0;i<=2e6;i++)down1[i]=down2[i]=hor[i]=-1;
for(auto x:mp){
int cur=x.first.first;
int p=x.first.second;
for(auto b:x.second)up[b].push_back(id+(b-cur)/p+1);
for(cur;cur<n;cur+=p){
id++;
if(id>1e7){
cout<<"assert\n";
return 0;
}
if(have[cur])down1[id]=cur;
if(cur!=x.first.first)hor[id-1]=id;
}
cur=x.first.first;
for(auto b:x.second)up[b].push_back(id+(b-cur)/p+1);
for(cur;cur<n;cur+=p){
id++;
if(id>1e7){
cout<<"assert\n";
return 0;
}
if(have[cur])down2[id]=cur;
if(cur!=x.first.first)hor[id]=id-1;
}
}
//assert(id<2e6);
if(id>1e7){
cout<<"assert\n";
return 0;
}
dis.resize(id+5,inf);
mp.clear();
dq.push_back({0,st});
while(!dq.empty()){
auto [d,u]=dq.front();
if(u>5e6){
cout<<"assert\n";
return 0;
}
if(u==-1){
cout<<"assert\n";
return 0;
}
dq.pop_front();
if(d>=dis[u])continue;
dis[u]=d;
//assert(u<2e6);
if(u==en)break;
if(u<n)for(auto x:up[u])dq.push_front({d,x});
/*for(auto x:down1[u])dq.push_front({d,x});
for(auto x:down2[u])dq.push_front({d,x});
for(auto x:hor[u])dq.push_back({d+1,x});*/
if(down1[u]!=-1)dq.push_front({d,down1[u]});
if(down2[u]!=-1)dq.push_front({d,down2[u]});
if(hor[u]!=-1)dq.push_back({d+1,hor[u]});
}
if(dis[en]==inf)cout<<-1;
else cout<<dis[en];
}
