#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e4, maxb = 175, maxv = 1.05e7, maxe = 2.1e7, magic = 1 << 20;
int n, m, cnt, bnd, s, t, l, r, Q[magic + 3], pnt[maxb + 3][maxn + 3], tot, msk[maxe + 3], nxt[maxe + 3], lnk[maxv + 3], dist[maxv + 3];
bool vis[maxb + 3][maxb + 3];
void add(int u, int v, int w) {
msk[++tot] = v * 2 + w;
nxt[tot] = lnk[u], lnk[u] = tot;
}
int main() {
scanf("%d %d", &n, &m);
cnt = n, bnd = sqrt(m) + .5;
for (int i = 1, b, p; i <= m; i++) {
scanf("%d %d", &b, &p);
b++;
if (i == 1) s = b;
if (i == 2) t = b;
if (p > bnd) {
int x = ++cnt, u = x, v;
add(b, x, 0);
for (int i = b - p; i >= 1; i -= p) {
v = ++cnt;
add(u, v, 1);
add(v, i, 0);
u = v;
}
u = x;
for (int i = b + p; i <= n; i += p) {
v = ++cnt;
add(u, v, 1);
add(v, i, 0);
u = v;
}
} else {
if (!vis[p][b % p]) {
vis[p][b % p] = 1;
int x = (b - 1) % p + 1;
for (int i = x; i <= n; i += p) {
add(pnt[p][i] = ++cnt, i, 0);
if (i > x) {
add(pnt[p][i], pnt[p][i - p], 1);
add(pnt[p][i - p], pnt[p][i], 1);
}
}
}
add(b, pnt[p][b], 0);
}
}
memset(dist, -1, sizeof(dist));
Q[r++] = s;
dist[s] = 0;
while (l != r) {
int u = Q[l++];
if (l == magic) l = 0;
if (u == t) break;
for (int i = lnk[u], v, w; i; i = nxt[i]) {
v = msk[i] >> 1, w = msk[i] & 1;
if (~dist[v]) continue;
dist[v] = dist[u] + w;
if (w) {
Q[r++] = v;
if (r == magic) r = 0;
} else {
if (--l < 0) l = magic - 1;
Q[l] = v;
}
}
}
printf("%d\n", dist[t]);
return 0;
}
