#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> v(n);
set<pair<int, int>> st;
int u, w;
for (int i = 0; i < m; i++) {
int b, p;
cin >> b >> p;
if (i == 0) u = b;
if (i == 1) w = b;
if (p >= n || st.find({b, p}) != st.end()) continue;
v[b].push_back(p);
st.insert({b, p});
}
for (int i = 0; i < n; i++) {
sort(v[i].rbegin(), v[i].rend());
}
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < n; i++) {
unordered_map<int, int> done;
for (int k : v[i]) {
for (int t = i % k; t < n; t += k) {
if (t != i) {
if (done[t]) continue;
done[t] = 1;
g[i].push_back({t, abs(i - t) / k});
}
}
}
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<int> d(n, inf);
pq.push({d[u] = 0, u});
while (pq.size()) {
auto [x, u] = pq.top();
pq.pop();
for (auto [v, w] : g[u]) {
if (d[v] > d[u] + w) {
pq.push({d[v] = d[u] + w, v});
}
}
}
cout << (d[w] == inf ? -1 : d[w]) << '\n';
return 0;
}
