#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <string.h>
#define N 30000
#define INF 0x3f3f3f3f
unsigned int X;
void srand_() {
struct timeval tv;
gettimeofday(&tv, NULL);
X = tv.tv_sec ^ tv.tv_usec | 1;
}
int rand_() {
return (X *= 3) >> 1;
}
int *ed[N], eo[N];
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ed[i] = (int *) realloc(ed[i], o * 2 * sizeof *ed[i]);
ed[i][o] = j;
}
void sort(int *aa, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, a_ = aa[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = aa[j] - a_;
if (c == 0)
j++;
else if (c < 0) {
tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
i++, j++;
} else {
k--;
tmp = aa[j], aa[j] = aa[k], aa[k] = tmp;
}
}
sort(aa, l, i);
l = k;
}
}
int find(int *aa, int n, int a) {
int lower = 0, upper = n - 1;
while (lower <= upper) {
int t = (lower + upper) / 2;
if (aa[t] < a)
lower = t + 1;
else if (aa[t] > a)
upper = t - 1;
else
return 1;
}
return 0;
}
int dd[N], pq[1 + N], iq[N], cnt;
int lt(int u, int v) {
return dd[u] < dd[v];
}
int i2(int i) {
return (i *= 2) > cnt ? 0 : i < cnt && lt(pq[i + 1], pq[i]) ? i + 1 : i;
}
void pq_up(int u) {
int i, j;
for (i = iq[u]; (j = i / 2) && lt(u, pq[j]); i = j)
pq[iq[pq[j]] = i] = pq[j];
pq[iq[u] = i] = u;
}
void pq_dn(int u) {
int i, j;
for (i = iq[u]; (j = i2(i)) && lt(pq[j], u); i = j)
pq[iq[pq[j]] = i] = pq[j];
pq[iq[u] = i] = u;
}
void pq_add(int u) {
iq[u] = ++cnt;
pq_up(u);
}
int pq_remove_first() {
int u = pq[1], v = pq[cnt--];
iq[v] = 1;
pq_dn(v);
return u;
}
int main() {
int n, m, i, j, w, d, d_, s, t;
srand_();
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++)
ed[i] = (int *) malloc(2 * sizeof *ed[i]), eo[i] = 0;
s = t = -1;
for (i = 0; i < m; i++) {
scanf("%d%d", &j, &d);
if (i == 0)
s = j;
else if (i == 1)
t = j;
append(j, d);
}
for (i = 0; i < n; i++) {
int o = 0;
sort(ed[i], 0, eo[i]);
for (j = 0; j < eo[i]; j++)
if (j == 0 || ed[i][j] != ed[i][j - 1])
ed[i][o++] = ed[i][j];
eo[i] = o;
}
memset(dd, 0x3f, n * sizeof *dd);
dd[s] = 0;
pq_add(s);
while (cnt) {
int o;
i = pq_remove_first();
for (o = eo[i]; o--; ) {
d = ed[i][o];
for (w = 0, j = i + d; j < n; j += d) {
w++;
d_ = dd[i] + w;
if (dd[j] == INF) {
dd[j] = d_;
pq_add(j);
} else if (d_ < dd[j]) {
dd[j] = d_;
pq_up(j);
}
if (find(ed[j], eo[j], d))
break;
}
for (w = 0, j = i - d; j >= 0; j -= d) {
w++;
d_ = dd[i] + w;
if (dd[j] == INF) {
dd[j] = d_;
pq_add(j);
} else if (d_ < dd[j]) {
dd[j] = d_;
pq_up(j);
}
if (find(ed[j], eo[j], d))
break;
}
}
}
printf("%d\n", dd[t] == INF ? -1 : dd[t]);
}
