#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b ; --i)
#define REP(i, a) for (int i = 0, _a = (a); i < _a; ++i)
#define pp pair<int, int>
#define bit(S, i) (((S) >> i) & 1)
#define next __next
#define prev __prev
#define N 30030
#define sqrtN 200
#define taskname ""
using namespace std;
int n, m, b[N], p[N];
struct data {
int u, jump;
long long d;
};
struct cmp{
bool operator() (const data &a, const data &b) {
return a.d > b.d;
}
};
priority_queue<data, vector<data>, cmp> heap;
long long d[N][sqrtN];
vector<int> smallJump[N], largeJump[N];//, smallJumpVer[N];
void Dijkstra(int start, int finish) {
REP(i, n) REP(j, (int)sqrt(n) + 1) d[i][j] = 1e18;
d[start][0] = 0;
heap.push(data({start, 0, 0}));
while (!heap.empty()) {
data u = heap.top();
heap.pop();
if (u.u == finish) {
cout << u.d;
return;
}
if (d[u.u][u.jump] != u.d) continue;
if (u.jump == 0) {
// Change value of jump
for (int jump : smallJump[u.u]) {
if (d[u.u][jump] > d[u.u][0]) {
d[u.u][jump] = d[u.u][0];
heap.push(data({u.u, jump, d[u.u][0]}));
}
}
// Large jump ( <= sqrt(n) times because jump > sqrt(n) )
for (int jump : largeJump[u.u]) {
int newU = u.u - jump, c = 0;
while (newU >= 0) {
++c;
if (d[newU][0] > d[u.u][0] + c) {
d[newU][0] = d[u.u][0] + c;
heap.push(data({newU, 0, d[newU][0]}));
}
newU -= jump;
}
newU = u.u + jump, c = 0;
while (newU < n) {
++c;
if (d[newU][0] > d[u.u][0] + c) {
d[newU][0] = d[u.u][0] + c;
heap.push(data({newU, 0, d[newU][0]}));
}
newU += jump;
}
}
}
else {
// Jump left - right
int newU = u.u - u.jump;
if (newU >= 0 && d[newU][u.jump] > d[u.u][u.jump] + 1) {
d[newU][u.jump] = d[u.u][u.jump] + 1;
heap.push(data({newU, u.jump, d[newU][u.jump]}));
}
newU = u.u + u.jump;
if (newU < n && d[newU][u.jump] > d[u.u][u.jump] + 1) {
d[newU][u.jump] = d[u.u][u.jump] + 1;
heap.push(data({newU, u.jump, d[newU][u.jump]}));
}
// Change Jump to 0
if (d[u.u][0] > d[u.u][u.jump]) {
d[u.u][0] = d[u.u][u.jump];
heap.push(data({u.u, 0, d[u.u][0]}));
}
}
}
cout << -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin >> n >> m;
int finish, start;
FOR(i, 1, m) {
int p, b;
cin >> b >> p;
if (i == 1) start = b;
if (i == 2) finish = b;
if (p <= (int) sqrt(n)) smallJump[b].push_back(p);
else largeJump[b].push_back(p);
}
Dijkstra(start, finish);
}
