#include <bits/stdc++.h>
#define int unsigned short
#define tiii tuple<int, int, int>
using namespace std;
int MXN = 30000;
int n, m, dis[30001][175], b, p, d=174, st, en;
vector<tiii> g[30001][175];
priority_queue<tiii, vector<tiii>, greater<tiii>> pq;
void dijkstra() {
pq.push({0, st, 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(cd > dis[cb][cp]) continue;
for(auto i: g[cb][cp]) {
int nd = cd+get<2>(i);
int nb = get<0>(i);
int np = get<1>(i);
if(nd < dis[nb][np]) {
dis[nb][np] = nd;
pq.push({nd, nb, np});
}
}
}
}
signed main() {
cin >> n >> m;
for(int i=0; i<sqrt(MXN); i++) {
for(int j=0; j<n; j++) {
if(j-i >= 0) {
g[j-i][i].push_back({j, i, 1});
}
if(j+i < n) {
g[j+i][i].push_back({j, i, 1});
}
g[j][i].push_back({j, 0, 0});
}
}
for(int i=0; i<30001; i++) {
for(int j=0; j<175; j++) {
dis[i][j] = 40000;
}
}
for(int i=0; i<m; i++) {
cin >> b >> p;
if(i == 0) st = b;
if(i == 1) en = b;
if(p >= sqrt(MXN)) {
int 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});
}
}
dijkstra();
if(dis[en][0] == 40000) cout << -1;
else cout << dis[en][0];
return 0;
}
