#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
vector<pii> a(m), adj[n];
map<int, bool> mp[n], alr[n];
for (auto &[x, y] : a) cin >> x >> y, mp[x][y] = true;
for (auto &[x, y] : a) {
if (alr[x].count(y)) continue;
alr[x][y] = true;
for (int i = x + y; i < n; i += y) {
adj[x].emplace_back((i - x) / y, i);
if (mp[i].count(y)) break;
}
for (int i = x - y; i >= 0; i -= y) {
adj[x].emplace_back((x - i) / y, i);
if (mp[i].count(y)) break;
}
}
priority_queue<pii> pq;
vector<int> dis(n, INT_MAX);
pq.emplace(0, a[0].first);
dis[a[0].first] = 0;
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (u == a[1].first) break;
if (dis[u] < -w) continue;
for (auto &[ww, v] : adj[u]) {
if (-w + ww >= dis[v]) continue;
dis[v] = -w + ww;
pq.emplace(-dis[v], v);
}
}
if (dis[a[1].first] == INT_MAX) cout << -1;
else cout << dis[a[1].first];
}
