#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
signed main(){
ios_base::sync_with_stdio();
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
vector <int> b(m),p(m);
set <int> s[n];
for(int i=0;i<m;i++){
cin>>b[i]>>p[i];
s[b[i]].insert(p[i]);
}
vector <pair <int,int> > g[n];
for(int i=0;i<n;i++){
for(auto x : s[i]){
int y=i+x,cnt=1;
if(y<n){
g[i].pb({y,1});
}
while(y+x<n){
cnt++;
if(s[y].find(x)==s[y].end()){
g[i].pb({y+x,cnt});
y+=x;
}else break;
}
y=i-x;cnt=1;
if(y>=0)g[i].pb({y,1});
while(y-x>=0){
cnt++;
if(s[y].find(x)==s[y].end()){
g[i].pb({y-x,cnt});
y-=x;
}else break;
}
}
}
set <pair <int,int> > st;
vector <int> d(n,1e12);
st.insert({0,b[0]});
d[b[0]]=0;
while(!st.empty()){
int v=st.begin()->second;
//cout<<v<<" "<<d[v]<<"\n";
st.erase(st.begin());
for(auto to : g[v]){
if(d[to.ff]>d[v]+to.ss){
st.erase({d[to.ff],to.ff});
d[to.ff]=d[v]+to.ss;
st.insert({d[to.ff],to.ff});
}
}
}
if(d[b[1]]==1e12)d[b[1]]=-1;
cout<<d[b[1]]<<"\n";
}
