#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")
using namespace std;
const int mxN = 30'000;
vector<int> all[mxN], init[mxN], l[mxN];
vector<int> dist[mxN];
bool vis[mxN];
int idx(int i, int j) {
return lower_bound(all[i].begin(), all[i].end(), j) - all[i].begin();
}
void testCase() {
int n, m;
cin >> n >> m;
vector<int> v;
while (m--) {
int b, p;
cin >> b >> p;
v.push_back(b);
init[b].push_back(p);
l[b % p].push_back(p);
}
for (int i = 0; i < n; i++) {
sort(l[i].begin(), l[i].end());
sort(init[i].begin(), init[i].end());
init[i].erase(unique(init[i].begin(), init[i].end()), init[i].end());
l[i].erase(unique(l[i].begin(), l[i].end()), l[i].end());
all[i] = l[i];
}
for (int i = 0; i < n; i++) {
for (int j : l[i]) {
for (int k = i; k < n; k += j) {
all[k].push_back(j);
}
}
sort(all[i].begin(), all[i].end());
dist[i].assign(all[i].size(), 1e9);
}
queue<tuple<int, int, int>> q;
for (auto p : init[v[0]]) {
vis[v[0]] = true;
int vv = idx(v[0], p);
q.push({v[0], p, vv});
dist[v[0]][vv] = 0;
}
while (!q.empty()) {
auto [u, p, id] = q.front();
q.pop();
int i;
if (u + p < n) i = idx(u + p, p);
if (u + p < n && dist[u + p][i] == 1e9) {
dist[u + p][i] = dist[u][id] + 1;
q.push({u + p, p, i});
}
if (u + p < n && !vis[u + p]) {
vis[u + p] = true;
for (int pp : init[u + p]) {
i = idx(u + p, pp);
if (dist[u + p][i] == 1e9) {
dist[u + p][i] = dist[u][id] + 1;
q.push({u + p, pp, i});
}
}
}
if (u - p >= 0) i = idx(u - p, p);
if (u - p >= 0 && dist[u - p][i] == 1e9) {
dist[u - p][i] = dist[u][id] + 1;
q.push({u - p, p, i});
}
if (u - p >= 0 && !vis[u - p]) {
vis[u - p] = true;
for (int pp : init[u - p]) {
i = idx(u - p, pp);
if (dist[u - p][i] == 1e9) {
dist[u - p][i] = dist[u][id] + 1;
q.push({u - p, pp, i});
}
}
}
}
dist[v[1]].push_back(1e9);
int ans = *min_element(dist[v[1]].begin(), dist[v[1]].end());
cout << (ans == 1e9 ? -1 : ans) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
testCase();
return 0;
}
