#include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; vector<int> a(m), b(m); for (int i = 0; i < m; i++) cin >> a[i] >> b[i]; int sn = sqrt(n * __lg(n)) + 1; vector<vector<int64_t>> d(n, vector<int64_t>(sn + 1, 9e18)); vector<vector<vector<tuple<int, int, int>>>> adj(n, vector<vector<tuple<int, int, int>>>(sn + 1)); for (int i = 0; i < m; i++) { if (b[i] < sn) { adj[a[i]][sn].emplace_back(a[i], b[i], 0); } else { for (int j = a[i] % b[i]; j < n; j += b[i]) { adj[a[i]][sn].emplace_back(j, sn, abs(a[i] - j) / b[i]); } } } d[a[0]][sn] = 0; priority_queue<tuple<int64_t, int, int>> pq; pq.emplace(0, a[0], sn); while (pq.size()) { auto [du, u, s] = pq.top(); pq.pop(); if (d[u][s] != -du) continue; du = -du; if (u == a[1]) return cout << du, 0; if (s != sn && u - s >= 0) { int uu = u - s, ss = s, c = 1; if (d[uu][ss] > du + c) { d[uu][ss] = du + c; pq.emplace(-d[uu][ss], uu, ss); } ss = sn; if (d[uu][ss] > du + c) { d[uu][ss] = du + c; pq.emplace(-d[uu][ss], uu, ss); } } if (s != sn && u + s < n) { int uu = u + s, ss = s, c = 1; if (d[uu][ss] > du + c) { d[uu][ss] = du + c; pq.emplace(-d[uu][ss], uu, ss); } ss = sn; if (d[uu][ss] > du + c) { d[uu][ss] = du + c; pq.emplace(-d[uu][ss], uu, ss); } } for (auto [uu, ss, c] : adj[u][s]) { if (d[uu][ss] > du + c) { d[uu][ss] = du + c; pq.emplace(-d[uu][ss], uu, ss); } } } cout << -1; }