#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
if (!(cin >> N >> M)) return 0;
vector<int> B(M), P(M);
for (int i = 0; i < M; ++i) cin >> B[i] >> P[i];
int Bsq = max(1, (int)floor(sqrt((double)N)));
// positions -> list of doges at that building
vector<vector<int>> pos_at(N);
for (int i = 0; i < M; ++i) pos_at[B[i]].push_back(i);
// dist for small states (pos, p) where p in [1..Bsq]
// encode idx = pos*(Bsq+1) + p (we ignore p=0)
int Pcount = Bsq + 1;
long long small_nodes = 1LL * N * Pcount;
vector<ll> dist_small;
dist_small.assign((size_t)small_nodes, INF);
// dist for doges (for any p > Bsq we store per-doge)
vector<ll> dist_doge(M, INF);
auto idx_small = [&](int pos, int p)->int{
return pos * Pcount + p;
};
// priority queue: tuple (dist, type, id, p_if_small)
// type: 0 = small state, id = pos, p given; 1 = doge state, id = doge index
using State = tuple<ll,int,int,int>;
// (dist, type, id, p)
priority_queue<State, vector<State>, greater<State>> pq;
// initial: doge 0 has news
if (P[0] <= Bsq) {
int id = idx_small(B[0], P[0]);
dist_small[id] = 0;
pq.emplace(0LL, 0, B[0], P[0]);
} else {
dist_doge[0] = 0;
pq.emplace(0LL, 1, 0, 0);
}
while (!pq.empty()) {
auto [d, type, id, p] = pq.top(); pq.pop();
if (type == 0) {
int pos = id;
int pp = p;
int id0 = idx_small(pos, pp);
if (d != dist_small[id0]) continue;
// If there are doges at this pos, we can pass news with cost 0
for (int doge : pos_at[pos]) {
if (P[doge] <= Bsq) {
int id2 = idx_small(pos, P[doge]);
if (dist_small[id2] > d) {
dist_small[id2] = d;
pq.emplace(d, 0, pos, P[doge]);
}
} else {
if (dist_doge[doge] > d) {
dist_doge[doge] = d;
pq.emplace(d, 1, doge, 0);
}
}
}
// Jump to pos +/- pp (cost 1 each)
int pos2 = pos + pp;
if (pos2 < N) {
int id2 = idx_small(pos2, pp);
if (dist_small[id2] > d + 1) {
dist_small[id2] = d + 1;
pq.emplace(d + 1, 0, pos2, pp);
}
}
pos2 = pos - pp;
if (pos2 >= 0) {
int id2 = idx_small(pos2, pp);
if (dist_small[id2] > d + 1) {
dist_small[id2] = d + 1;
pq.emplace(d + 1, 0, pos2, pp);
}
}
} else {
int u = id;
if (d != dist_doge[u]) continue;
if (u == 1) { // reached doge 1
cout << d << '\n';
return 0;
}
int step = P[u];
int posu = B[u];
// enumerate reachable positions x = posu +/- k*step
// cost increases by k (number of jumps)
// go right
ll k = 1;
for (ll x = (ll)posu + step; x < N; x += step, ++k) {
ll nd = d + k;
if (step <= Bsq) {
int id2 = idx_small((int)x, step);
if (dist_small[id2] > nd) {
dist_small[id2] = nd;
pq.emplace(nd, 0, (int)x, step);
}
}
// if any doge at x, we can pass to it
for (int doge : pos_at[x]) {
if (dist_doge[doge] > nd) {
dist_doge[doge] = nd;
pq.emplace(nd, 1, doge, 0);
}
}
}
// go left
k = 1;
for (ll x = (ll)posu - step; x >= 0; x -= step, ++k) {
ll nd = d + k;
if (step <= Bsq) {
int id2 = idx_small((int)x, step);
if (dist_small[id2] > nd) {
dist_small[id2] = nd;
pq.emplace(nd, 0, (int)x, step);
}
}
for (int doge : pos_at[x]) {
if (dist_doge[doge] > nd) {
dist_doge[doge] = nd;
pq.emplace(nd, 1, doge, 0);
}
}
}
}
}
// if never reached doge 1
if (dist_doge[1] == INF) cout << -1 << '\n';
else cout << dist_doge[1] << '\n';
return 0;
}
