#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<int, int>
const int mxN = 3e4 + 5;
using namespace std;
struct node{
int q,p;
};
vector<pair<node,int>>v[mxN][100];
int pos[mxN];
int dist[mxN][100];
bool operator<(pair<node,int>a,pair<node,int>b){
return a.S > b.S;
}
signed main(){
int n,m;
cin >>n>>m;
int buck = 99;
for(int p = 1;p <= buck;p++){
for(int i = 0;i < n;i++){
if(i + p < n){
v[i][p].push_back({{i + p,p},1});
v[i + p][p].push_back({{i,p},1});
}
v[i][p].push_back({{i,0},0});
}
}
for(int i = 0;i < m;i++){
int q,p;
cin >>q>>p;
pos[i] = q;
if(p <= buck){
v[q][0].push_back({{q,p},0});
}else{
int cnt = 1;
for(int j = q - p;j >= 0;j -= p){
v[q][0].push_back({{j,0},cnt});
cnt++;
}
cnt = 1;
for(int j = q + p;j < n;j += p){
v[q][0].push_back({{j,0},cnt});
cnt++;
}
}
}
for(int i = 0;i < n;i++){
for(int p = 0;p <= buck;p++){
dist[i][p] = 1e9;
}
}
dist[pos[0]][0] = 0;
priority_queue<pair<node,int>>q;
q.push({{pos[0],0},0});
while(q.size()){
auto u = q.top();
// cout<<u.F.q<<' '<<u.F.p<<' '<<u.S<<'\n';
q.pop();
if(dist[u.F.q][u.F.p] < u.S) continue;
for(auto x : v[u.F.q][u.F.p]){
if(dist[x.F.q][x.F.p] > u.S + x.S){
dist[x.F.q][x.F.p] = u.S + x.S;
q.push({{x.F},dist[x.F.q][x.F.p]});
}
}
}
cout<<(dist[pos[1]][0] == 1e9 ? -1 : dist[pos[1]][0]);
}
