#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define ll int
#define ss second
#define ff first
#define INF 2000000000000000
#define pb push_back
#define edge pair<ll, pair<ll,ll> > // une, number ,power
#define cost first
#define num second.first
#define pwr second.second
ll n,m,l,r,i,j,ii,jj,k,x,y,D[30005][201],s,e;
vector< edge > v[30005][201]; // number , power (powergu oroi bol power = 179)
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>m;
for(i=1;i<=m;i++){
cin>>l>>r;
if(i==1) s=l;
if(i==2) e=l;
if(r>199)
for(j=1 ; l+r*j<n || l-r*j>=0 ; j++){
edge a;
a.num=l+r*j;
a.pwr=200;
a.cost=j;
if(a.num<n) v[l][200].pb(a);
a.num=l-r*j;
if(a.num>=0) v[l][200].pb(a);
}
else{
v[l][200].pb({0,{l,r}});
}
}
priority_queue<edge , vector< edge >, greater< edge > > q;
memset(D,-1,sizeof(D));
q.push({0,{s,200}});
while(!q.empty()){
ll une, nmbr, power;
une=q.top().cost;
nmbr=q.top().num;
power=q.top().pwr;
if(nmbr==e){
cout<<une;
return 0;
}
q.pop();
if(D[nmbr][power]!=-1);
else{
D[nmbr][power]=une;
for(edge no : v[nmbr][power]) if(D[no.num][no.pwr]==-1) q.push({une+no.cost,{no.num,no.pwr}});
if(power!=200){
if(D[nmbr][200]==-1) q.push({une,{nmbr,200}});
if(nmbr+power<n && D[nmbr+power][power]==-1) q.push({une+1,{nmbr+power,power}});
if(nmbr-power>=0 && D[nmbr-power][power]==-1) q.push({une+1,{nmbr-power,power}});
}
}
}
cout<<D[e][200];
}
