#include <iostream>
#include <queue>
#include <vector>
#include <map>
using namespace std;
int N, M, A[30009], P[30009]; vector<int>G[30009], dist[30009]; vector<vector<pair<int, 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(make_pair(qx, qy));
}
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++) {
cin >> A[i] >> P[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;
for (int j = A[i] % P[i]; j < N; j += P[i]) G[i].push_back(j);
X[i].resize(G[i].size());
dist[i].resize(G[i].size(), (1 << 30));
for (int j = 0; j < G[i].size(); j++) {
if (j == 0 || j + 1 == G[i].size()) X[i][j].resize(2);
else X[i][j].resize(4);
int cnt = 0;
if (j + 1 < G[i].size()) {
X[i][j][cnt] = make_pair(i, j + 1); cnt++;
X[i][j][cnt] = make_pair(0, G[i][j + 1]); cnt++;
}
if (j >= 1) {
X[i][j][cnt] = make_pair(i, j - 1); cnt++;
X[i][j][cnt] = make_pair(0, G[i][j - 1]); cnt++;
}
}
}
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();
for (int i = 0; i < X[pos1][pos2].size(); i++) {
int to1 = X[pos1][pos2][i].first, to2 = X[pos1][pos2][i].second;
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;
}
