#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int minimumJumps (int l, int r, int start, int objective, vector<vector<int>> & skycrapers) {
// make the bfs:
int n = (int)skycrapers.size();
vector<bool> visited(n, false);
priority_queue<pair<int, int>> queueBFS; // {jumps, position}
queueBFS.push(make_pair(0, start));
int jumps, idx;
while (!queueBFS.empty()) {
jumps = -queueBFS.top().first;
idx = queueBFS.top().second;
queueBFS.pop();
// check if we arrived at pos1
if (idx == objective) {
return jumps;
}
visited[idx] = true;
// visit all conections:
for (int p: skycrapers[idx]) {
if (p == 0) {
continue; // this doge has null movement
}
// to the left:
int left = idx - p;
for (int i = 1; l <= left; i++) {
if (!skycrapers[left].empty() && !visited[left]) {
queueBFS.push(make_pair(-(jumps+i), left));
}
left -= p;
}
// to the right:
int right = idx + p;
for (int i = 1; right <= r; i++) {
if (!skycrapers[right].empty() && !visited[right]) {
queueBFS.push(make_pair(-(jumps+i), right));
}
right += p;
}
}
}
// if we arrive at here there is no possible path:
return -1;
}
int main() {
// ios::sync_with_stdio(false);
// cin.tie(NULL);
// input:
int n, m, x, p, pos0, pos1;
cin >> n >> m;
vector<vector<int>> skycrapers(n, vector<int>());
// doge 0:
cin >> x >> p;
skycrapers[x].push_back(p);
pos0 = x;
// doge 1:
cin >> x >> p;
skycrapers[x].push_back(p);
pos1 = x;
// other doges:
m -= 2;
for (int i = 0; i < m; i++) {
cin >> x >> p;
skycrapers[x].push_back(p);
}
// call function:
cout << minimumJumps(0, n-1, pos0, pos1, skycrapers) << '\n';
return 0;
}
