#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mxN = 3e4+5;
int n, m, sqT;
map <pair <int, int>, set <int>> adj;
set <int> ID[mxN];
ll dis[mxN];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
sqT = ceil(sqrt(n));
pair <int, int> a[m];
for (int idx = 0; idx < m; idx++) {
auto &[p, q] = a[idx];
cin >> p >> q;
ID[p].emplace(idx);
for (int i = 1; i <= sqT; i++) adj[{p%i, i}].emplace(idx);
}
for (int i = 0; i < m; i++) dis[i] = LLONG_MAX;
dis[0] = 0;
priority_queue <pair <ll, int>> q;
q.emplace(0, 0);
while (q.size()) {
auto [w, u] = q.top(); q.pop();
w = -w;
if (dis[u] != w) continue;
if (u == 1) {
cout << w << '\n';
return 0;
}
ID[a[u].first].erase(ID[a[u].first].find(u));
for (int i = 1; i <= sqT; i++) adj[{a[u].first % i, i}].erase(adj[{a[u].first % i, i}].find(u));
if (a[u].second <= sqT) {
for (auto &v : adj[{a[u].first % a[u].second, a[u].second}]) if (v != u) {
ll nw = w + abs(a[u].first - a[v].first) / a[u].second;
if (dis[v] > nw) q.emplace(-(dis[v] = nw), v);
}
} else {
for (int it = a[u].first; it < n; it += a[u].second) for (auto v : ID[it]) if (v != u) {
ll nw = w + abs(a[u].first - a[v].first) / a[u].second;
if (dis[v] > nw) q.emplace(-(dis[v] = nw), v);
}
for (int it = a[u].first - a[u].second; it >= 0; it -= a[u].second) for (auto v : ID[it]) if (v != u) {
ll nw = w + abs(a[u].first - a[v].first) / a[u].second;
if (dis[v] > nw) q.emplace(-(dis[v] = nw), v);
}
}
}
cout << -1 << '\n';
}
