#include <bits/stdc++.h>
using namespace std;
const int inf = int(1e9);
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> v(n);
int start = 0, end = 0;
for (int i = 0; i < m; i++) {
int b, p;
cin >> b >> p;
if (i == 0) {
start = b;
} else if (i == 1) {
end = b;
}
v[b].push_back(p);
}
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
int d = abs(i - j);
int mx = 0;
for (int p : v[i]) {
if (d % p == 0) {
mx = max(mx, p);
}
}
if (mx > 0) {
g[i].emplace_back(j, d / mx);
}
}
}
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;
}
