#include <bits/stdc++.h>
using namespace std;
const int nax = 3e4 + 5;
vector<pair<int, int>> doges[nax];
const int B = 175;
vector<array<int, 3>> edges[nax][B];
bool has[nax][B];
int ans[nax][B];
void solve () {
int n, m;
cin >> n >> m;
int start, finish;
for (int i = 0; i < m; ++i) {
int b, p;
cin >> b >> p;
if (i == 0) start = b;
if (i == 1) finish = b;
if (p <= B) {
has[b][p] = 1;
} else {
for (int j = b + p; j < n; j += p) {
edges[b][0].push_back({j, 0,(j - b) / p});
}
for (int j = b - p; j >= 0; j -= p) {
edges[b][0].push_back({j, 0, (b - j) / p});
}
}
}
for (int i = 0; i < n; ++i) {
ans[i][0] = 1e9;
for (int j = 1; j < B; ++j) {
if (has[i][j]) {
edges[i][0].push_back({i, j, 0});
}
edges[i][j].push_back({i, 0, 0});
ans[i][j] = 1e9;
}
}
priority_queue<array<int, 3>> pq;
pq.push({0, start, 0});
ans[start][0] = 0;
int answer = -1;
while (!pq.empty()) {
array<int, 3> a = pq.top();
pq.pop();
int dist = a[0], u = a[1], p = a[2];
//cout << dist << ' ' << u << ' ' << p << '\n';
if (u == finish) {
answer = dist;
break;
}
if (ans[u][p] != dist) continue;
for (array<int, 3> v : edges[u][p]) {
if (ans[v[0]][v[1]] > dist + v[2]) {
pq.push({ans[v[0]][v[1]] = dist + v[2], v[0], v[1]});
}
}
if (p != 0 && u + p < n && ans[u + p][p] > dist + 1) {
pq.push({ans[u + p][p] = dist + 1, u + p, p});
}
if (p != 0 && u - p >= 0 && ans[u - p][p] > dist + 1) {
pq.push({ans[u - p][p] = dist + 1, u - p, p});
}
}
cout << answer;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
}
