#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;
const int MAXN = 30010;
int B[MAXN], P[MAXN];
int n, m;
vector <pair <int, int> > ve[MAXN];
set <pair <int, int> > se;
int dist[MAXN];
int bio[MAXN];
set <int> E[MAXN];
int main() {
ios_base::sync_with_stdio(false);
cin >> n >> m;
REP(i, m) {
cin >> B[i] >> P[i];
E[B[i]].insert(P[i]);
}
REP(i, n) {
REP(j, n) {
int d = 1e9;
for (int t : E[i]) {
if (abs(i - j) % t == 0) d = min(d, abs(i - j) / t);
}
if (d != 1e9) ve[i].push_back({j, d});
}
}
REP(i, n) dist[i] = 1e9;
dist[B[0]] = 0;
REP(i, n) se.insert({dist[i], i});
while (se.size()) {
auto tr = *se.begin();
se.erase(se.begin());
int x = tr.second, D = tr.first;
bio[x] = 1;
if (x == B[1]) continue;
for (auto t : ve[x]) {
int y = t.first, d = t.second;
if (dist[y] > D + d) {
assert(bio[y] == 0);
se.erase({dist[y], y});
dist[y] = D + d;
se.insert({dist[y], y});
}
}
}
if (dist[B[1]] >= 1e9) cout << "-1\n";
else cout << dist[B[1]] << "\n";
return 0;
}
