#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
struct cell
{
int to,st,tim,ind;
bool operator<(const cell&a)const
{
return a.tim<tim;
}
};
int n,m,used[505][505],ti[100005],dogtim[100005];
cell a[100005];
vector<cell>v[100005];
priority_queue<cell>q;
void prec()
{
for(int i=1;i<=n;i++)
{
ti[i]=1e9;
}
for(int j=1;j<=m;j++)
{
dogtim[j]=1e9;
}
dogtim[1]=0;
ti[a[1].to]=0;
}
void dijkstra()
{
cell w,nb;
int start=a[1].to;
for(int i=0;i<v[start].size();i++)
{
nb.st=v[start][i].st;
nb.to=v[start][i].to;
nb.tim=ti[start];
nb.ind=v[start][i].ind;
q.push(nb);
}
int izm=0;
while(!q.empty())
{
w=q.top();
q.pop();
if(w.ind==2)
{
cout<<w.tim<<endl;
exit(0);
}
if(dogtim[w.ind]<w.tim)continue;
if(w.st<300)
{
if(used[w.st][w.to%w.st])continue;
used[w.st][w.to%w.st]=1;
}
izm=0;
for(int i=w.to+w.st;i<=n;i+=w.st)
{
izm++;
if(ti[i]<=w.tim+izm)continue;
ti[i]=w.tim+izm;
//cout<<w.ind<<" "<<i<<" "<<w.to<<" "<<w.st<<endl;
for(int j=0;j<v[i].size();j++)
{
nb.st=v[i][j].st;
nb.to=i;
nb.tim=ti[i];
nb.ind=v[i][j].ind;
q.push(nb);
dogtim[v[i][j].ind]=ti[i];
}
}
izm=0;
for(int i=w.to-w.st;i>=1;i-=w.st)
{
izm++;
if(ti[i]<=w.tim+izm)continue;
ti[i]=w.tim+izm;
for(int j=0;j<v[i].size();j++)
{
nb.st=v[i][j].st;
nb.to=i;
nb.tim=ti[i];
nb.ind=v[i][j].ind;
q.push(nb);
dogtim[v[i][j].ind]=ti[i];
}
}
}
}
void read()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a[i].to>>a[i].st;
a[i].to++;
a[i].ind=i;
v[a[i].to].push_back(a[i]);
}
cout<<endl;
prec();
dijkstra();
cout<<-1<<endl;
}
int main()
{
speed();
read();
return 0;
}
