#include <bits/stdc++.h>
#define int short
#define tiii pair<short, pair<short, short>>
using namespace std;
short MXN = 30000;
short n, m, dis[30001][175], b, p, d=174, st, en, cnt, cd, cb, cp, nd, nb, np;;
vector<tiii> g[30001][175];
priority_queue<tiii, vector<tiii>, greater<tiii>> pq;
signed main() {
cin >> n >> m;
for(int i=0; i<30001; i++) {
fill(dis[i], dis[i] + 175, 32700);
}
for(int i=0; i<m; i++) {
cin >> b >> p;
if(i == 0) st = b;
if(i == 1) en = b;
if(p >= sqrt(MXN)) {
cnt = 0;
for(int j=b; j<n; j+=p) {
g[b][d].push_back({j, {0, cnt}});
cnt++;
}
cnt = 1;
for(int j=b-p; j>=0; j-=p) {
g[b][d].push_back({j, {0, cnt}});
cnt++;
}
g[b][0].push_back({b, {d, 0}});
} else {
g[b][0].push_back({b, {p, 0}});
}
}
pq.push({0, {st, 0}});
while(pq.size()) {
cd = pq.top().first;
cb = pq.top().second.first;
cp = pq.top().second.second;
pq.pop();
if(cd > dis[cb][cp] || cd > dis[cb][0]) continue;
for(auto i: g[cb][cp]) {
nd = cd+i.second.second;
nb = i.first;
np = i.second.first;
if(nd < dis[nb][np]) {
dis[nb][np] = nd;
pq.push({nd, {nb, np}});
}
}
if(cp != 0 && cp != d && cb-cp >= 0) {
if(cd+1 < dis[cb-cp][cp]) {
dis[cb-cp][cp] = cd+1;
pq.push({cd+1, {cb-cp, cp}});
}
}
if(cp != 0 && cp != d && cb+cp < n) {
if(cd+1 < dis[cb+cp][cp]) {
dis[cb+cp][cp] = cd+1;
pq.push({cd+1, {cb+cp, cp}});
}
}
if(cp != 0 && cd < dis[cb][0]) {
dis[cb][0] = cd;
pq.push({cd, {cb, 0}});
}
}
if(dis[en][0] == 32700) cout << -1;
else cout << dis[en][0];
return 0;
}
