#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 30000 + 10; const int inf = 1e9; int b[maxn], p[maxn], dp[maxn], mark[maxn]; vector<int> vec[maxn]; int main(){ ios_base::sync_with_stdio(false); int n, m; cin >> n >> m; for (int i = 0; i < m; i++){ cin >> b[i] >> p[i]; vec[b[i]].push_back(p[i]); } for (int i = 0; i < n; i++) dp[i] = inf; dp[b[0]] = 0; int cnt = 0; for (int _ = 0; _ < n; _++){ cnt ++; int v = -1; for (int i = 0; i < n; i++) if (!mark[i] and (v == -1 or dp[v] > dp[i])) v = i; if (dp[v] == inf) return cout << -1 << endl, 0; if (v == b[1]) return cout << dp[v] << endl, 0; if (cnt == 10000){ if (dp[b[1]] == inf) dp[b[1]] = -1; return cout << dp[b[1]] << endl, 0; } mark[v] = 1; for (auto u : vec[v]){ for (int idx = v + u; idx < n; idx += u) dp[idx] = min(dp[idx], dp[v] + (idx - v) / u); for (int idx = v - u; idx >= 0; idx -= u) dp[idx] = min(dp[idx], dp[v] + (v - idx) / u); } } }