#include <bits/stdc++.h>
#define tiii tuple<int, int, int>
using namespace std;
int MXN = 30000;
int n, m, dis[30010][200], st, en;
vector<int> g[30010];
priority_queue<tiii, vector<tiii>, greater<tiii>> pq;
void relax(int nb, int np, int nd) {
if(nd < dis[nb][np]) {
dis[nb][np] = nd;
pq.push({nd, nb, np});
}
}
void dijkstra() {
pq.push({0, st, 0});
dis[st][0] = 0;
while(pq.size()) {
int cd = get<0>(pq.top());
int cb = get<1>(pq.top());
int cp = get<2>(pq.top());
pq.pop();
if(cp == 0) {
for(auto i: g[cb]) {
if(i >= sqrt(MXN)) {
int cnt = 1;
for(int j=cb+i; j<n; j+=i) {
relax(j, 0, cd+cnt);
cnt++;
}
cnt = 1;
for(int j=cb-i; j>=0; j-=i) {
relax(j, 0, cd+cnt);
cnt++;
}
} else {
relax(cb, i, cd);
}
}
} else {
if(cb-cp >= 0) relax(cb-cp, cp, cd+1);
if(cb+cp < n) relax(cb+cp, cp, cd+1);
relax(cb, 0, cd);
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i=0; i<30010; i++) {
for(int j=0; j<200; j++) {
dis[i][j] = 1e9;
}
}
for(int i=0; i<m; i++) {
int b, p;
cin >> b >> p;
if(i == 0) st = b;
if(i == 1) en = b;
g[b].push_back(p);
}
dijkstra();
if(dis[en][0] == 1e9) cout << -1;
else cout << dis[en][0];
return 0;
}
