#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10;
vector<pair<int,int>> adj[N];
int d[N];
//check if it has p[i] in that node already or not
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
vector<pair<int,int>> v;
bool vs[N];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m,st,ed,a,b,tmp,u;
cin>>n >>m;
for(int i=0;i<m;i++){
cin>>b >>a;
if(i==0) st=b;
if(i==1) ed=b;
//p[i],pos[i]
v.push_back({a,b});
}
if(m==1){
cout<<-1;
return 0;
}
//cout<<st <<" " <<ed <<"\n";
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
for(auto [pow,pos]:v){
//forward
for(int i=pos+pow;i<n;i+=pow){
tmp=(i-pos)/pow;
adj[pos].push_back({i,tmp});
if(*(lower_bound(v.begin(),v.end(),make_pair(pow,i)))==make_pair(pow,i)) break;
//cout<<pos <<" " <<i <<" " <<tmp <<"\n";
}
//backward
for(int i=pos-pow;i>=0;i-=pow){
tmp=(pos-i)/pow;
adj[pos].push_back({i,tmp});
if(*(lower_bound(v.begin(),v.end(),make_pair(pow,i)))==make_pair(pow,i)) break;
//cout<<pos <<" " <<i <<" " <<tmp <<"\n";
}
}
for(int i=0;i<n;i++) d[i]=INT_MAX;
d[st]=0;
q.push({0,st});
while(!q.empty()){
u=q.top().second;
q.pop();
if(vs[u]) continue;
vs[u]=true;
for(auto [v,w]:adj[u]){
if(d[u]+w<d[v]){
d[v]=d[u]+w;
q.push({d[v],v});
}
}
}
if(d[ed]==INT_MAX) cout<<-1;
else cout<<d[ed];
}
