#include <iostream>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#pragma warning (disable: 4996)
int N, M, A[30009], P[30009]; vector<short>G[30009]; vector<int>dist[30009]; vector<vector<int>> X[30009];
map<pair<int, int>, int>M1; queue<pair<int, int>>Q;
void connect(int px, int py, int qx, int qy) {
X[px][py].emplace_back((qx << 15) + qy);
}
int constant(int u1, int u2) {
return (u1 << 15) + u2;
}
int main() {
cin >> N >> M;
for (int i = 0; i < N; i++) G[0].push_back(i);
X[0].resize(G[0].size());
dist[0].resize(G[0].size(), (1 << 30));
for (int i = 1; i <= M; i++) scanf("%d%d", &A[i], &P[i]);
for (int i = 1; i <= M; i++) {
int J = M1[make_pair(A[i] % P[i], P[i])];
if (J == 0) {
M1[make_pair(A[i] % P[i], P[i])] = i; J = i; int BB = A[i] % P[i];
G[i].resize(((N - 1) - BB) / P[i] + 1);
int CC = 0; for (int j = A[i] % P[i]; j < N; j += P[i]) { G[i][CC] = j; CC++; }
dist[i].resize(G[i].size(), (1 << 30));
}
int pos1 = lower_bound(G[J].begin(), G[J].end(), A[i]) - G[J].begin();
if (A[i] + P[i] < N) connect(0, A[i], 0, A[i] + P[i]);
if (A[i] - P[i] >= 0) connect(0, A[i], 0, A[i] - P[i]);
if (pos1 >= 1) connect(0, A[i], J, pos1 - 1);
if (pos1 + 1 < G[J].size()) connect(0, A[i], J, pos1 + 1);
}
dist[0][A[1]] = 0; Q.push(make_pair(0, A[1]));
while (!Q.empty()) {
int pos1 = Q.front().first, pos2 = Q.front().second; Q.pop();
if (pos1 == 0 && pos2 == A[2]) break;
if (pos1 == 0) {
for (int i = 0; i < X[pos1][pos2].size(); i++) {
int D = X[pos1][pos2][i];
int to1 = (D >> 15), to2 = (D & 32767);
if (dist[to1][to2] > dist[pos1][pos2] + 1) {
dist[to1][to2] = dist[pos1][pos2] + 1;
Q.push(make_pair(to1, to2));
}
}
}
if (pos1 >= 1) {
for (int j = -1; j <= 1; j += 2) {
int to1 = pos1, to2 = pos2 + j; if (to2 < 0 || to2 >= G[pos1].size()) continue;
if (dist[to1][to2] > dist[pos1][pos2] + 1) {
dist[to1][to2] = dist[pos1][pos2] + 1;
Q.push(make_pair(to1, to2));
}
}
for (int j = -1; j <= 1; j += 2) {
int to1 = pos1, to2 = pos2 + j; if (to2 < 0 || to2 >= G[pos1].size()) continue;
to2 = G[to1][to2]; to1 = 0;
if (dist[to1][to2] > dist[pos1][pos2] + 1) {
dist[to1][to2] = dist[pos1][pos2] + 1;
Q.push(make_pair(to1, to2));
}
}
}
}
if (dist[0][A[2]] == (1 << 30)) dist[0][A[2]] = -1;
cout << dist[0][A[2]] << endl;
return 0;
}
