#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>
using namespace std;
long long N, M, A[30009], P[30009]; int cnt = 0;
vector<int>X[30009];
map<pair<long long, long long>, int>MM, MM2, dist; queue<pair<int, int>>Q;
void refresh(int to, int dst, int val) {
if (to < 0 || to >= N) return;
int F = dist[make_pair(to, dst)];
if (F == 0) {
dist[make_pair(to, dst)] = val;
Q.push(make_pair(to, dst));
}
}
int main() {
cin >> N >> M;
for (int i = 1; i <= M; i++) {
cin >> A[i] >> P[i];
long long G = A[i] % P[i]; MM2[make_pair(A[i], P[i])] = 1;
if (MM[make_pair(G, P[i])] == 1) continue;
MM[make_pair(G, P[i])] = 1;
for (int j = G; j + P[i] < N; j++) {
X[j].push_back(j + P[i]);
X[j + P[i]].push_back(j);
}
}
Q.push(make_pair(A[1], 0)); dist[make_pair(A[1], 0)] = 1;
while (!Q.empty()) {
pair<int, int> pos1 = Q.front(); Q.pop();
int pos = pos1.first, state = pos1.second;
if (state == 0) {
for (int i = 0; i < X[pos].size(); i++) {
int to = X[pos][i], dst = abs(pos - to); cnt++; if (MM2[make_pair(pos, dst)] == 0) continue;
refresh(to, dst, dist[pos1] + 1);
refresh(to, 0, dist[pos1] + 1);
}
}
else {
refresh(pos - state, state, dist[pos1] + 1);
refresh(pos + state, state, dist[pos1] + 1);
refresh(pos - state, 0, dist[pos1] + 1);
refresh(pos + state, 0, dist[pos1] + 1);
}
}
cout << dist[make_pair(A[2], 0)] - 1 << endl;
return 0;
}
