#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int,int> pp;
typedef vector<int> vec;
typedef vector<vec> mat;
#define pb push_back
#define B 170
int N,M;
int a[30010],P[30010];
int dist[30010];
bool chk[30010][B];
priority_queue<pp,vector<pp>,greater<pp> > Q;
mat doge;
int main(){
scanf("%d%d",&N,&M);
doge.assign(N,vec());
for(int i=0;i<M;i++){
scanf("%d%d",&a[i],&P[i]);
doge[a[i]].push_back(P[i]);
if(P[i]<B){
chk[a[i]][P[i]]=1;
}
}
memset(dist,0x3f,sizeof(dist));
int INF=dist[0];
dist[a[0]]=0;
Q.push(pp(0,a[0]));
int v,d;
while(!Q.empty()){
v=Q.top().second;d=Q.top().first;Q.pop();
if(dist[v]!=d)continue;
if(v==a[1])break;
for(int k=0;k<doge[v].size();k++){
int p=doge[v][k];
for(int i=v+p;i<N;i+=p){
if(dist[i]>dist[v]+(i-v)/p){
dist[i]=dist[v]+(i-v)/p;
Q.push(pp(dist[i],i));
if(p<B&&chk[i][p])break;
if(p<B)chk[i][p]=1;
}
}
for(int i=v-p;i>=0;i-=p){
if(dist[i]>dist[v]+(v-i)/p){
dist[i]=dist[v]+(v-i)/p;
Q.push(pp(dist[i],i));
if(p<B&&chk[i][p])break;
if(p<B)chk[i][p]=1;
}
}
}
}
if(dist[a[1]]==INF){
puts("-1");
}else{
printf("%d",dist[a[1]]);
}
}
