// #pragma optimize("Ofast")
#include "bits/stdc++.h"
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define em emplace_back
#define mp make_pair
#define F first
#define S second
using namespace std;
template<class C>
using vec = vector<C>;
using vi = vector<int>;
using vpi = vector<pair<int, int> >;
using pii = pair<int, int>;
#ifdef LOCAL
const int N = 100;
#else
const int N = 30001;
#endif
const int sqr = 170;
int cnt = 0;
int n, m;
int id[sqr][N];
vec<vpi> g;
int dijkstra(int s, int t) {
vi dp(cnt, INT_MAX);
dp[s] = 0;
set<pii> q;
q.emplace(0, s);
while (!q.empty()) {
auto [d,v] = *q.begin();
q.erase(q.begin());
for (auto& [to, w] : g[v]) {
int relax = d + w;
if (dp[to] > relax) {
q.erase({dp[to], to});
q.emplace(dp[to] = relax, to);
}
}
}
return dp[t];
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < sqr; i++) {
for (int j = 0; j < n; j++) {
id[i][j] = cnt++;
}
}
g.resize(cnt);
for (int i = 1; i < sqr; i++) {
for (int j = 0; j < n; j++) {
g[id[i][j]].em(id[0][j], 0);
if (j - i >= 0) g[id[i][j]].em(id[i][j - i], 1);
if (j + i < n) g[id[i][j]].em(id[i][j + i], 1);
}
}
vi bb(m), pp(m);
for (int i = 0; i < m; i++) {
int b, p;
cin >> b >> p;
bb[i] = b;
pp[i] = p;
if (p >= sqr) {
for (int j = b % p; j < n; j += p) {
int w = abs(j - b) / p;
g[id[0][b]].em(id[0][j], w);
}
} else {
g[id[0][b]].em(id[p][b], 0);
}
}
int ans = dijkstra(id[0][bb[0]], id[0][bb[1]]);
if (ans == INT_MAX) {
cout << -1 << '\n';
} else {
cout << ans << '\n';
}
}
