#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
const int nmax=30005;
const int buck=200;
vector<int> v[nmax],mare[nmax];
bool E[nmax];
int d[nmax][buck+5];
int n,m,i,j,wh,x,cost,use,fin,k,val,md;
struct node
{
int fi,se,cat;
};
struct cmp
{
bool operator() (node unu,node doi)
{
return unu.cat>doi.cat;
}
};
priority_queue< node,vector<node>, cmp > pq;
void prp(int a,int b,int dist)
{
if(dist<d[a][b])
{
d[a][b]=dist;
pq.push({a,b,d[a][b]});
}
}
int abss(int x)
{
if(x<0) return -x;
return x;
}
int dij()
{
while(!pq.empty())
{
i=pq.top().fi;
j=pq.top().se;
cost=pq.top().cat;
pq.pop();
if(cost==d[i][j])
{
if(i==fin)
return cost;
if(i-j>=0) prp(i-j,j,cost+1);
if(i+j<n) prp(i+j,j,cost+1);
for(k=0; k<v[i].size(); k++)
prp(i,v[i][k],cost);
if(!E[i])
{
E[i]=1;
for(k=0; k<mare[i].size(); k++)
{
E[i]=1;
val=mare[i][k];
md=i%val;
for(j=md; j<n; j+=val)
prp(j,0,cost+abss(j-md)/val);
}
}
}
}
return -1;
}
int main()
{
// freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n>>m;
for(i=0;i<n;i++)
for(j=0;j<=buck;j++)
d[i][j]=INT_MAX;
for(i=0;i<m;i++)
{
cin>>wh>>x;
if(x<=buck) v[wh].push_back(x);
else mare[wh].push_back(x);
if(i==0)
pq.push({wh,x,0}),d[wh][x]=0;
if(i==1)
fin=wh;
}
cout<<dij();
return 0;
}
