//https://oj.uz/problem/view/APIO15_skyscraper
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define st first
#define nd second
#define pii pair<int,int>
int n,m;
int root;
//position / power
struct E{
int pos;
int pow;
int waga;
};
struct Node{
int d;
int pos;
int pow;
};
class comp{
public:
bool operator()(Node A,Node B){
return A.d<B.d;
}
};
vector<E> edges[30009][174];
int dis[30009][174];
void build(){
for(int i=0;i<n;i++){
for(int j=1;j<=root;j++){
edges[i][j].pb({i,0,0});
}
}
}
void addsmaller(int pos,int pow){
int pos2 = pos;
while(pos2+pow<n){
edges[pos2][pow].pb({pos2+pow,pow,1});
pos2 += pow;
}
pos2 = pos;
while(pos2-pow>=0){
edges[pos2][pow].pb({pos2-pow,pow,1});
pos2 -= pow;
}
}
void addbigger(int pos,int pow){
int pos2 = pos;
int dl = 1;
while(pos2+pow<n){
edges[pos][pow].pb({pos2+pow,0,dl});
pos2 += pow;
dl++;
}
pos2 = pos;
dl = 1;
while(pos2-pow>=0){
edges[pos][pow].pb({pos2-pow,0,dl});
pos2 -= pow;
dl++;
}
}
void dijkstra(pii pocz){
priority_queue<Node,vector<Node>,comp> q;
q.push({0,pocz.st,pocz.nd});
while(!q.empty()){
auto t = q.top();
q.pop();
t.d = -t.d;
if(dis[t.pos][t.pow] != t.d)
continue;
for(auto x:edges[t.pos][t.pow]){
if(t.d + x.waga < dis[x.pos][x.pow]){
dis[x.pos][x.pow] = t.d + x.waga;
q.push({-dis[x.pos][x.pow],x.pos,x.pow});
}
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n>>m;
root = (int)sqrt(n);
build();
pii zero,one;
for(int i=0;i<m;i++){
int pos,pow;
cin>>pos>>pow;
edges[pos][0].pb({pos,pow,0});
if(pow <= root){
addsmaller(pos,pow);
} else{
addbigger(pos,pow);
}
if(i>1) continue;
if(i == 0){
zero = {pos,pow};
} else if(i == 1){
one = {pos,pow};
}
}
for(int i=0;i<n;i++){
for(int j=0;j<=root;j++){
dis[i][j] = 1000000000;
}
}
dis[zero.st][zero.nd] = 0;
dijkstra(zero);
/*for(int i=0;i<n;i++){
for(int j=0;j<=n;j++){
cout<<"pos: "<<i<<" pow: "<<j<<endl;
for(auto x:edges[i][j]){
cout<<"pos: "<<x.pos<<" pow: "<<x.pow<<" waga: "<<x.waga<<endl;
}
}
}*/
if(dis[one.st][one.nd] == 1000000000){
cout<<"-1\n";
} else cout<<dis[one.st][one.nd]<<endl;
return 0;
}
