#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <string.h>
int min(int a, int b) { return a < b ? a : b; }
#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;
}
struct L {
struct L *next;
int j, w;
} *ej[N];
void link(int i, int j, int w) {
struct L *l = (struct L *) calloc(1, sizeof *l);
l->j = j, l->w = w;
l->next = ej[i];
ej[i] = l;
};
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() {
static int jj[N], ww[N];
int n, m, i, j, 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++)
sort(ed[i], 0, eo[i]);
memset(ww, -1, n * sizeof *ww);
for (i = 0; i < n; i++) {
int o, o_;
o_ = 0;
for (o = eo[i]; o--; ) {
d = ed[i][o];
if (o + 1 < eo[i] && d == ed[i][o + 1])
continue;
for (j = i + d; j < n; j += d) {
if (ww[j] == -1) {
jj[o_++] = j;
ww[j] = (j - i) / d;
} else
ww[j] = min(ww[j], (j - i) / d);
if (find(ed[j], eo[j], d))
break;
}
for (j = i - d; j >= 0; j -= d) {
if (ww[j] == -1) {
jj[o_++] = j;
ww[j] = (i - j) / d;
} else
ww[j] = min(ww[j], (i - j) / d);
if (find(ed[j], eo[j], d))
break;
}
}
for (o = 0; o < o_; o++) {
j = jj[o];
link(i, j, ww[j]);
ww[j] = -1;
}
}
memset(dd, 0x3f, n * sizeof *dd);
dd[s] = 0;
pq_add(s);
while (cnt) {
struct L *l;
i = pq_remove_first();
for (l = ej[i]; l; l = l->next) {
d = dd[i] + l->w;
if (dd[l->j] == INF) {
dd[l->j] = d;
pq_add(l->j);
} else if (d < dd[l->j]) {
dd[l->j] = d;
pq_up(l->j);
}
}
}
printf("%d\n", dd[t] == INF ? -1 : dd[t]);
}
