#include <bits/stdc++.h>
using namespace std;
struct edge_add {
vector<int> to, nx;
vector<int> hd;
edge_add(int n) : hd(n, -1) {}
inline void push(int u, int v, int w) { // w ∈ {0,1}
to.push_back((v << 1) | w);
nx.push_back(hd[u]);
hd[u] = static_cast<int>(to.size()) - 1;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
vector<int> b(m), p(m);
for (int i = 0; i < m; ++i) cin >> b[i] >> p[i];
const int SQ = static_cast<int>(sqrt(n)) + 1;
/* grafikni qurish */
edge_add g(n); // avval faqat binolar (0..n-1)
vector<int> dist(n, -1);
/* kichik kuchlar (p ≤ SQ) uchun: har p va qoldiq r bo‘yicha tuzilma */
vector<vector<char>> vis(SQ + 1);
vector<unordered_map<int, int>> mp(SQ + 1);
for (int i = 1; i <= SQ; ++i) vis[i].assign(i, 0);
auto new_node = [&](edge_add &gr, vector<int> &d) -> int {
int id = static_cast<int>(gr.hd.size());
gr.hd.push_back(-1);
d.push_back(-1);
return id;
};
/* barchasini ketma‑ket quramiz */
for (int i = 0; i < m; ++i) {
int bi = b[i], pi = p[i];
if (pi <= SQ) { // kichik kuch
int r = bi % pi;
if (!vis[pi][r]) { // shu (pi,r) guruhi ilgari qurilmagan
vis[pi][r] = 1;
int prv = -1;
for (int x = r; x < n; x += pi) {
int v = new_node(g, dist); // guruh tuguni
g.push(v, x, 0); // tugun → bino (0)
if (prv != -1) {
g.push(v, prv, 1); // qo‘shni tugunlar (1)
g.push(prv, v, 1);
}
mp[pi][x] = v; // (pi, x) ↦ id
prv = v;
}
}
g.push(bi, mp[pi][bi], 0); // bino → guruh (0)
} else { // katta kuch (pi > SQ)
int root = new_node(g, dist);
g.push(bi, root, 0); // bino → ildiz (0)
/* chapga zanjir */
int u = root;
for (int x = bi - pi; x >= 0; x -= pi) {
int v = new_node(g, dist);
g.push(u, v, 1); // zanjir bo‘ylab (1)
g.push(v, x, 0); // tugun → bino (0)
u = v;
}
/* o‘ngga zanjir */
u = root;
for (int x = bi + pi; x < n; x += pi) {
int v = new_node(g, dist);
g.push(u, v, 1);
g.push(v, x, 0);
u = v;
}
}
}
/* 0‑1 BFS (deque) */
deque<int> dq;
dist[b[0]] = 0;
dq.push_front(b[0]);
while (!dq.empty()) {
int u = dq.front();
dq.pop_front();
for (int e = g.hd[u]; e != -1; e = g.nx[e]) {
int v = g.to[e] >> 1;
int w = g.to[e] & 1;
if (dist[v] == -1 || dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
if (w == 0) dq.push_front(v);
else dq.push_back(v);
}
}
}
cout << dist[b[1]] << '\n'; // dist[–1] bo‘lsa ‑1 chiqadi
return 0;
}
