#include <iostream> #include <queue> #include <set> #include <vector> using namespace std; priority_queue<pair<int, int>> q1; const int MAXN = 30010; set<int> v1[MAXN]; vector<pair<int, int>> g[MAXN]; bool visited[MAXN]; int dp[MAXN]; int target; int first, jump; int main() { int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int b, p; cin >> b >> p; if (i == 0) { first = b; jump = p; } if (i == 1) { target = b; } v1[b].insert(p); } for (int i = 0; i <= n; i++) { for (int x : v1[i]) { int b = i; int p = x; int count = 1; for (int j = b + p; j <= n; j += p) { // cout<<i<<" "<<j<<endl; if (v1[j].find(p) != v1[j].end()) { g[b].push_back(make_pair(j, count)); break; } g[b].push_back(make_pair(j, count)); count++; } count = 1; for (int j = b - p; j >= 0; j -= p) { if (v1[j].find(p) != v1[j].end()) { g[b].push_back(make_pair(j, count)); break; } g[b].push_back(make_pair(j, count)); count++; } } } q1.push(make_pair(0, first)); for (int i = 0; i <= n; i++) { dp[i] = 1e9; } dp[first] = 0; while (!q1.empty()) { auto hold = q1.top(); int skyscraper = hold.second; int dist = -1 * hold.first; q1.pop(); if (skyscraper == target) { cout << dist << endl; return 0; } if (visited[skyscraper]) { continue; } visited[skyscraper] = true; for (auto x : g[skyscraper]) { int w = x.second; int to = x.first; if (dp[to] > dp[skyscraper] + w) { dp[to] = dp[skyscraper] + w; q1.push(make_pair(-1 * dp[to], to)); } } } cout << -1 << endl; }