#include <iostream>
#include <cmath>
using namespace std;
long long int n,m,t[1000005][3],b[30005],p[30005],f[30005][405],ga[30005][405],road[30005],map[30005],tag[30005];
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)road[i]=-1;
for(int i=0;i<m;i++)
{
cin>>b[i]>>p[i];
map[i]=road[b[i]];
road[b[i]]=i;
}
for(int i=0;i<30000;i++)
{
for(int j=0;j<400;j++)
{
f[i][j]=-1;
ga[i][j]=-1;
}
}
if(p[0]<=sqrt(n))
{
t[0][0]=b[0];
t[0][1]=p[0];
t[0][2]=2;
ga[b[0]][p[0]]=0;
}
else
{
t[0][0]=0;
t[0][1]=200;
t[0][2]=1;
f[0][200]=0;
}
tag[b[0]]=1;
int g=road[b[0]];
int pp=0,qq=0;
while(g!=-1)
{
int now=g;
if(now!=0)
{
qq++;
if(p[now]<=sqrt(n) && ga[b[now]][p[now]]==-1)
{
t[qq][0]=b[now];
t[qq][1]=p[now];
t[qq][2]=2;
ga[b[now]][p[now]]=0;
}
else
{
t[qq][0]=now;
t[qq][1]=200;
t[qq][2]=1;
f[now][200]=0;
}
}
g=map[g];
}
while(pp<=qq)
{
//cout<<"st "<<pp<<" "<<qq<<endl;
//cout<<t[pp][0]<<" "<<t[pp][1]<<" "<<t[pp][2]<<endl;
//if(t[pp][2]==1)cout<<f[t[pp][0]][t[pp][1]]<<endl;
//else cout<<ga[t[pp][0]][t[pp][1]]<<endl;
if(t[pp][2]==1)
{
int i=t[pp][0];
int l=b[i]+(200-t[pp][1]-1)*p[i],r=b[i]+(200-t[pp][1]+1)*p[i];
if(l>=0 && f[t[qq][0]][t[qq][1]]==-1)
{
qq++;
t[qq][0]=t[pp][0];
t[qq][1]=t[pp][1]-1;
t[qq][2]=1;
f[t[qq][0]][t[qq][1]]=f[t[pp][0]][t[pp][1]]+1;
}
if(l>=0 && tag[l]==0)
{
tag[l]=1;
int g=road[l];
while(g!=-1)
{
int now=g;
qq++;
//cout<<"ok"<<"1 "<<g<<" "<<l<<endl;
if(p[now]<=sqrt(n) && ga[b[now]][p[now]]==-1)
{
t[qq][0]=b[now];
t[qq][1]=p[now];
t[qq][2]=2;
ga[b[now]][p[now]]=f[t[pp][0]][t[pp][1]]+1;
}
else
{
t[qq][0]=now;
t[qq][1]=200;
t[qq][2]=1;
f[now][200]=f[t[pp][0]][t[pp][1]]+1;
}
g=map[g];
}
}
if(r<n && f[t[qq][0]][t[qq][1]]==-1)
{
qq++;
t[qq][0]=t[pp][0];
t[qq][1]=t[pp][1]+1;
t[qq][2]=1;
f[t[qq][0]][t[qq][1]]=f[t[pp][0]][t[pp][1]]+1;
//cout<<"f"<<" "<<f[t[qq][0]][t[qq][1]]<<" "<<t[qq][0]<<" "<<t[qq][1]<<endl;
}
if(r<n && tag[r]==0)
{
tag[r]=1;
int g=road[r];
while(g!=-1)
{
int now=g;
qq++;
//cout<<"ok"<<"2 "<<g<<" "<<r<<endl;
if(p[now]<=sqrt(n) && ga[b[now]][p[now]]==-1)
{
t[qq][0]=b[now];
t[qq][1]=p[now];
t[qq][2]=2;
ga[b[now]][p[now]]=f[t[pp][0]][t[pp][1]]+1;
}
else
{
t[qq][0]=now;
t[qq][1]=200;
t[qq][2]=1;
f[now][200]=f[t[pp][0]][t[pp][1]]+1;
}
g=map[g];
}
}
}
else
{
int l=t[pp][0]-t[pp][1],r=t[pp][0]+t[pp][1];
if(l>=0 && ga[l][t[pp][1]]==-1)
{
qq++;
t[qq][0]=l;
t[qq][1]=t[pp][1];
t[qq][2]=2;
ga[l][t[pp][1]]=ga[t[pp][0]][t[pp][1]]+1;
}
if(l>=0 && tag[l]==0)
{
tag[l]=1;
int g=road[l];
while(g!=-1)
{
//cout<<"ok"<<"3 "<<g<<" "<<l<<endl;
int now=g;
qq++;
if(p[now]<=sqrt(n) && ga[b[now]][p[now]]==-1)
{
t[qq][0]=b[now];
t[qq][1]=p[now];
t[qq][2]=2;
ga[b[now]][p[now]]=ga[t[pp][0]][t[pp][1]]+1;
}
else
{
t[qq][0]=now;
t[qq][1]=200;
t[qq][2]=1;
f[now][200]=ga[t[pp][0]][t[pp][1]]+1;
}
g=map[g];
}
}
if(r<n && ga[r][t[pp][1]]==-1)
{
qq++;
t[qq][0]=r;
t[qq][1]=t[pp][1];
t[qq][2]=2;
ga[r][t[pp][1]]=ga[t[pp][0]][t[pp][1]]+1;
}
if(r<n && tag[r]==0)
{
tag[r]=1;
int g=road[r];
while(g!=-1)
{
//cout<<"ok"<<"4 "<<g<<" "<<r<<endl;
int now=g;
qq++;
if(p[now]<=sqrt(n) && ga[b[now]][p[now]]==-1)
{
t[qq][0]=b[now];
t[qq][1]=p[now];
t[qq][2]=2;
ga[b[now]][p[now]]=ga[t[pp][0]][t[pp][1]]+1;
}
else
{
t[qq][0]=now;
t[qq][1]=200;
t[qq][2]=1;
f[now][200]=ga[t[pp][0]][t[pp][1]]+1;
}
g=map[g];
}
}
}
pp++;
}
long long int ans=999999999;
for(int i=0;i<400;i++)
{
if(f[1][i]!=-1)ans=min(ans,f[1][i]);
}
for(int i=0;i<=300;i++)
{
if(ga[b[1]][i]!=-1)ans=min(ans,ga[b[1]][i]);
}
if(ans==999999999)cout<<"-1";
else cout<<ans;
}
