#include <bits/stdc++.h>
using namespace std;
const int inf = int(1e9);
const int S = 170;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
int start = 0, end = 0;
vector is(n, vector<int>(S));
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; i++) {
int b, p;
cin >> b >> p;
if (i == 0) {
start = b;
} else if (i == 1) {
end = b;
}
if (p >= S) {
for (int j = b - p; j >= 0; j -= p) {
g[b].emplace_back(j, (b - j) / p);
}
for (int j = b + p; j < n; j += p) {
g[b].emplace_back(j, (j - b) / p);
}
} else {
is[b][p] = 1;
}
}
for (int b = 0; b < n; b++) {
for (int p = 0; p < S; p++) {
if (!is[b][p]) continue;
for (int j = b - p; j >= 0; j -= p) {
g[b].emplace_back(j, (b - j) / p);
if (is[j][p]) break;
}
for (int j = b + p; j < n; j += p) {
g[b].emplace_back(j, (j - b) / p);
if (is[j][b]) break;
}
}
}
priority_queue<pair<int, int>> pq;
vector<int> dist(n, inf);
vector<int> vis(n);
pq.emplace(0, start);
dist[start] = 0;
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (vis[u]) continue;
if (u == end) {
cout << -d << '\n';
return 0;
}
vis[u] = 1;
for (auto [v, w] : g[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.emplace(-dist[v], v);
}
}
}
cout << -1 << '\n';
return 0;
}
