#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int NMAX = 30001;
bool used[NMAX][151];
bool use1[NMAX][151];
vector <vector <int> > vv(NMAX);
vector <pii> g[NMAX];
int d[NMAX][151];
int main(){
int n; cin >> n;
int m; cin >> m;
int b[m + 1], p[m + 1];
for(int i = 0; i < m; i++){
cin >> b[i] >> p[i];
if(p[i] > 150){
int x = b[i] - p[i];
int cnt = 1;
while(x >= 0){
g[b[i]].pb({x, cnt++});
x -= p[i];
}
x = b[i] + p[i];
cnt = 1;
while(x < n){
g[b[i]].pb({x, cnt++});
x += p[i];
}
continue;
}
if(!use1[b[i]][p[i]])
use1[b[i]][p[i]] = true, vv[b[i]].pb(p[i]);
}
for(int i = 0; i < n; i++){
for(int j = 0; j <= 150; j++)
d[i][j] = 1e9;
}
d[b[0]][0] = 0;
priority_queue<pair<int, pii> > q;
q.push({0, {b[0], 0}});
while(!q.empty()){
int x = q.top().s.s, v = q.top().s.f;
q.pop();
if(used[v][x]) continue;
used[v][x] = true;
if(x == 0){
for(int to : vv[v]){
if(d[v][to] > d[v][x])
d[v][to] = d[v][x], q.push({-d[v][to], {v, to}});
}
for(auto to : g[v]){
if(d[to.f][0] > d[v][x] + to.s)
d[to.f][0] = d[v][x] + to.s, q.push({-d[to.f][0], {to.f,0}});
}
}
else{
if(d[v][0] > d[v][x])
d[v][0] = d[v][x], q.push({-d[v][0], {v, 0}});
if(v >= x && d[v - x][x] > d[v][x] + 1)
d[v - x][x] = d[v][x] + 1, q.push({-d[v - x][x], {v - x, x}});
if(v + x < n && d[v + x][x] > d[v][x] + 1)
d[v + x][x] = d[v][x] + 1, q.push({-d[v + x][x], {v + x, x}});
}
}
if(d[b[1]][0] == 1e9)
d[b[1]][0] = -1;
cout << d[b[1]][0];
return 0;
}
