#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <bitset>
using namespace std;
const int MAXN = 30100;
const int SQN = 40;
const int INF = 1e9 + 177013;
pair<int, int> dogs[MAXN];
vector<int> jlen[MAXN];
bitset<MAXN> used;
int dist[MAXN][SQN];
void update(int i, int p, int d, set<pair<int, pair<int, int>>>& rdist) {
if (dist[i][p] > d) {
dist[i][p] = d;
rdist.insert({d, {i, p}});
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> dogs[i].first >> dogs[i].second;
jlen[dogs[i].first].push_back(dogs[i].second);
}
int s = dogs[0].first;
int t = dogs[1].first;
for (int i = 0; i < n; ++i) {
for (int d = 0; d < SQN; ++d) {
dist[i][d] = INF;
}
}
dist[s][0] = 0;
set<pair<int, pair<int, int>>> rdist;
rdist.insert({0, {s, 0}});
while (rdist.size()) {
auto [d, ip] = *rdist.begin();
auto [i, p] = ip;
rdist.erase(rdist.begin());
if (dist[i][p] < d)
continue;
update(i, 0, d, rdist);
if (p == 0) {
for (auto np : jlen[i]) {
if (np < SQN) {
update(i, np, d, rdist);
continue;
}
for (int j = i % np; j < n; j += np) {
update(j, 0, d + abs(i - j) / np, rdist);
}
}
} else {
if (i >= p)
update(i - p, p, d + 1, rdist);
if (i + p < n)
update(i + p, p, d + 1, rdist);
}
}
if (dist[t][0] >= INF)
cout << "-1\n";
else
cout << dist[t][0] << '\n';
}
