#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int max_ans = 5000000;
const int maxN = 30005;
const int maxSqrtN = 200;
int n,m;
int zero,one;
int root;
vector<int> powers[maxN];
vector<ll> q[max_ans];
bool done[maxN][maxSqrtN];
ll Encode(int building,int power){
assert(power <= maxSqrtN);
return building + n*power;
}
int dijkstra(){
int curr_ans = 0;
int best_ans = -1;
q[0].pb(Encode(zero,0));
while(curr_ans < max_ans){
if(q[curr_ans].empty()){
curr_ans++;
continue;
}
ll top = q[curr_ans].back();
q[curr_ans].pop_back();
int building = top%n;
int power = top/n;
if(done[building][power]) continue;
done[building][power] = true;
if(building == one){
if(best_ans == -1){
best_ans = curr_ans;
}
continue;
}
//in building
if(!power){
for(ll doge:powers[building]){
//doge in building
if(doge<=root){
q[curr_ans].pb(Encode(building,doge));
} else{
//other building (power>root)
for(int dir=-1;dir<2;dir+=2){
for(int jumps=1;;jumps++){
int pos = building + jumps*dir*doge;
if(pos<0 || pos>=n) break;
q[curr_ans+jumps].pb(Encode(pos,0));
}
}
}
}
} else{
//doge with power <= root
//to building
q[curr_ans].pb(Encode(building,0));
//to other doge
int pos = building + power;
if(pos<n) q[curr_ans+1].pb(Encode(pos,power));
pos = building - power;
if(pos>=0) q[curr_ans+1].pb(Encode(pos,power));
}
}
return best_ans;
}
int main(){
cin>>n>>m;
root = (int)sqrt(n);
for(int i=0;i<m;i++){
int building,power;
cin>>building>>power;
powers[building].pb(power);
if(i==0) zero = building;
if(i==1) one = building;
}
cout<<dijkstra();
return 0;
}
