#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// #define int ll
#define pb push_back
typedef pair<int, int> pii;
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
const int INF = 1e9;
bool cmin(int &a, const int &b) {
if (a > b) {
a = b;
return 1;
}
return 0;
}
void run() {
int n, m;
cin >> n >> m;
vector<int> b(m), p(m);
vector<vector<int>> who(n);
for (int i = 0; i < m; ++i) {
cin >> b[i] >> p[i];
who[b[i]].pb(p[i]);
}
vector<vector<pii>> g(n);
vector<int> used(n, -1);
for (int u = 0; u < n; ++u) {
sort(all(who[u]));
who[u].resize(unique(all(who[u])) - who[u].begin());
for (auto x : who[u]) {
int cnt = 1;
for (int i = u + x; i < n; i += x) {
if (used[i] != u) {
g[u].pb({i, cnt});
used[i] = u;
}
++cnt;
}
cnt = 1;
for (int i = u - x; i >= 0; i -= x) {
if (used[i] != u) {
g[u].pb({i, cnt});
used[i] = u;
}
++cnt;
}
}
sort(all(g[u]));
g[u].resize(unique(all(g[u])) - g[u].begin());
}
vector<int> dist(n, INF);
priority_queue<pii> q;
dist[b[0]] = 0;
q.push({0, b[0]});
while (!q.empty()) {
pii pr = q.top();
q.pop();
if (-pr.F != dist[pr.S])
continue;
int u = pr.S;
for (auto edge : g[u]) {
int v = edge.F;
int w = edge.S;
if (cmin(dist[v], dist[u] + w)) {
q.push({-dist[v], v});
}
}
}
if (dist[b[1]] >= INF)
dist[b[1]] = -1;
cout << dist[b[1]] << '\n';
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
run();
}
