#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pb push_back
#define B begin()
#define E end()
using namespace std;
int a[300010];
int b[300010];
//vector<pair<int,int>>v[100100];
int dist(int i,int j)
{
return abs(a[j]-a[i]);
}
int gg[2002][2002];
int dis[100100];
const int inf=1e17;
signed main()
{
ios_base::sync_with_stdio();
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
gg[i][j] = inf;
}
}
int ss=0,ee=0;
for(int i=1; i<=m; i++)
{
cin>>a[i]>>b[i];
if(i==1)
ss=a[i];
if(i==2)
ee=a[i];
}
for(int i=1; i<=m; i++)
{
int g=0;
for(int j=a[i]-b[i]; j>=0; j-=b[i])
{
g++;
//cout<<" "<<a[i]<<" "<<j<<" "<<g<<endl;
gg[a[i]][j]=min(gg[a[i]][j],g);
}
g=1;
for(int j=a[i]+b[i]; j<n; j+=b[i])
{
// cout<<" "<<a[i]<<" "<<j<<" "<<g<<endl;
gg[a[i]][j]=min(gg[a[i]][j],g);
g++;
}
}
if(ss==ee)
{
cout<<0<<endl;
return 0;
}
for(int i=0; i<=n+1; i++)
{
dis[i]=inf;
}
dis[ss]=0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
q.push({0,ss});
while(!q.empty())
{
// cout<<"D";
pair<int,int>x=q.top();
q.pop();
// cout<<" :::: "<<x.S<<endl;
for(int i=0;i<n;i++)
{
if(i==x.S)
continue;
int ned=x.F+gg[x.S][i]; // cout<<" "<<i.F<<" "<<ned<<endl;
if(ned<dis[i])
{
//cout<<" "<<i.S<<" "<<ned<<" "<<
dis[i]=ned;
q.push({ned,i});
}
}
}
if(dis[ee]<inf)
cout<<dis[ee]<<endl;
else
cout<<-1<<endl;
}
