#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int radical=2001,N=3e4+1;
vector<int>adj[N];
int dp[N][radical+1],n,m,best[N];
struct merg
{
int nod,val,cost;
};
void asoc(int &a,int &b,int &c,merg x)
{
a=x.nod;
b=x.val;
c=x.cost;
}
void init(int n)
{
for(int i=1; i<=n; i++)
best[i]=1e9;
for(int i=1; i<=n; i++)
for(int j=1; j<=radical; j++)
dp[i][j]=1e9;
}
struct doge
{
int poz,val;
} dog[N];
void citeste()
{
cin>>n>>m;
init(n);
for(int i=1; i<=m; i++)
{
int a,b;
cin>>dog[i].poz>>dog[i].val;
dog[i].poz++;
adj[dog[i].poz].push_back(dog[i].val);
}
}
void rezolva()
{
queue<merg>q;
q.push({dog[1].poz,dog[1].val,0});
while(!q.empty())
{
int nod,valoare,cost;
asoc(nod,valoare,cost,q.front());
best[nod]=min(best[nod],cost);
if(valoare!=-1)
{
if(nod+valoare<=n && dp[nod+valoare][valoare]>cost+1)
{
dp[nod+valoare][valoare]=cost+1;
q.push({nod+valoare,valoare,cost+1});
}
if(nod-valoare>=1 && dp[nod-valoare][valoare]>cost+1)
{
dp[nod-valoare][valoare]=cost+1;
q.push({nod-valoare,valoare,cost+1});
}
}
for(auto u:adj[nod])
{
dp[nod][u]=min(dp[nod][u],cost);
if(u>radical)
{
for(int j=nod+u; j<=n; j+=u)
{
if(best[j]>cost+1)
{
best[j]=cost+1;
q.push({j,-1,cost+1});
}
}
for(int j=nod-u; j>=1; j-=u)
{
if(best[j]>cost+1)
{
best[j]=cost+1;
q.push({j,-1,cost+1});
}
}
}
else
{
if(nod+u<=n &&dp[nod+u][u]>cost+1)
{
dp[nod+u][u]=cost+1;
q.push({nod+u,u,cost+1});
}
if(nod-u>=1&&dp[nod-u][u]>cost+1)
{
dp[nod-u][u]=cost+1;
q.push({nod-u,u,cost+1});
}
}
}
q.pop();
}
if(best[dog[2].poz]==1e9)
cout<<-1<<'\n';
else
cout<<best[dog[2].poz]<<'\n';
}
int main()
{
citeste();
rezolva();
return 0;
}
