#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]; 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]; for (int i = 0; i < m; i++) dp[i] = inf; dp[0] = 0; for (int _ = 0; _ < m; _++){ int v = -1; for (int i = 0; i < m; 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 == 1) return cout << dp[1] << endl, 0; mark[v] = 1; for (int u = 0; u < m; u++){ if (mark[u]) continue; if (abs(b[v] - b[u]) % p[v] == 0) dp[u] = min(dp[u], dp[v] + abs(b[v] - b[u]) / p[v]); } } }