#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <limits>
using namespace std;
bool cmpPair(const pair<int,int> &a, const pair<int,int> &b) {
return a.first > b.first;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<int> B(M), P(M);
for (int i = 0; i < M; ++i) {
cin >> B[i] >> P[i];
}
int K = static_cast<int>(sqrt(N)) + 1;
vector<bool> smallFlag(K + 1, false);
for (int i = 0; i < M; ++i) {
if (P[i] <= K) {
smallFlag[P[i]] = true;
}
}
vector<int> smallPs;
for (int p = 1; p <= K; ++p) {
if (smallFlag[p]) {
smallPs.push_back(p);
}
}
// bucket[p][r] = list of doge indices j with B[j] % p == r
vector< vector< vector<int> > > bucket(K + 1);
for (int pi : smallPs) {
bucket[pi].assign(pi, vector<int>());
}
for (int j = 0; j < M; ++j) {
for (int pi : smallPs) {
int r = B[j] % pi;
bucket[pi][r].push_back(j);
}
}
// map of building -> doges initially there
vector< vector<int> > building2doge(N);
for (int j = 0; j < M; ++j) {
building2doge[B[j]].push_back(j);
}
const int INF = numeric_limits<int>::max() / 2;
vector<int> dist(M, INF);
vector<bool> visited(M, false);
// for small P, track which (p,r) we've scanned
vector< vector<bool> > usedSmall(K + 1);
for (int pi : smallPs) {
usedSmall[pi].assign(pi, false);
}
priority_queue< pair<int,int>, vector<pair<int,int>>, decltype(&cmpPair) > pq(cmpPair);
dist[0] = 0;
pq.push(make_pair(0, 0));
while (!pq.empty()) {
pair<int,int> cur = pq.top();
pq.pop();
int d = cur.first;
int i = cur.second;
if (visited[i]) {
continue;
}
visited[i] = true;
if (i == 1) {
break;
}
int bi = B[i];
int pi = P[i];
if (pi <= K) {
int r = bi % pi;
if (!usedSmall[pi][r]) {
usedSmall[pi][r] = true;
vector<int> &grp = bucket[pi][r];
for (int j : grp) {
if (!visited[j]) {
int w = abs(B[j] - bi) / pi;
int nd = d + w;
if (nd < dist[j]) {
dist[j] = nd;
pq.push(make_pair(nd, j));
}
}
}
// clear to save memory
grp.clear();
}
} else {
int step = 1;
int pos = bi + pi;
while (pos < N) {
int w = step;
for (int j : building2doge[pos]) {
if (!visited[j]) {
int nd = d + w;
if (nd < dist[j]) {
dist[j] = nd;
pq.push(make_pair(nd, j));
}
}
}
++step;
pos += pi;
}
step = 1;
pos = bi - pi;
while (pos >= 0) {
int w = step;
for (int j : building2doge[pos]) {
if (!visited[j]) {
int nd = d + w;
if (nd < dist[j]) {
dist[j] = nd;
pq.push(make_pair(nd, j));
}
}
}
++step;
pos -= pi;
}
}
}
if (dist[1] >= INF) {
cout << -1;
} else {
cout << dist[1];
}
return 0;
}
