#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
using namespace std;
typedef pair<int,int> ppair;
vector<int>v[30010];
priority_queue<ppair, vector<ppair>, greater<ppair> >q;
int ch[30010],val,x,y,pos,n,m,t,en,arr[200][30010],d[30010];
int main()
{
int i,j;
scanf("%d %d",&n,&m);
t=sqrt(n);
for(i=1;i<=m;i++){
scanf("%d %d",&x,&y); v[++x].push_back(y);
if(i==1) pos=x;
if(i==2) en=x;
}
for(i=1;i<=n;i++) d[i]=1e9; d[pos]=0; ch[pos]=1;
while(1)
{
for(i=0;i<v[pos].size();i++)
{
val=v[pos][i];
if(val<=t)
{
if(arr[val][pos]) continue;
arr[val][pos]=1;
for(j=pos+val;j<=n;j+=val){
if(d[j]>d[pos]+(j-pos)/val){d[j]=d[pos]+(j-pos)/val; q.push(make_pair(d[pos]+(j-pos)/val,j));}
arr[val][j]=1;
}
for(j=pos-val;j>=1;j-=val){
if(d[j]>d[pos]+(j-pos)/val){d[j]=d[pos]-(j-pos)/val; q.push(make_pair(d[pos]-(j-pos)/val,j));}
arr[val][j]=1;
}
}
else
{
for(j=pos+val;j<=n;j+=val){
if(d[j]>d[pos]+(j-pos)/val){d[j]=d[pos]+(j-pos)/val; q.push(make_pair(d[pos]+(j-pos)/val,j));}
}
for(j=pos-val;j>=1;j-=val){
if(d[j]>d[pos]+(j-pos)/val){d[j]=d[pos]-(j-pos)/val; q.push(make_pair(d[pos]-(j-pos)/val,j));}
}
}
}
while(q.size() && ch[q.top().second]) q.pop();
if(q.size()==0) break;
pos=q.top().second; d[pos]=q.top().first; ch[pos]=1;
if(q.top().second==en) break;
}
if(d[en]==1e9) printf("-1");
else printf("%d",d[en]);
return 0;
}
