#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
const int maxn = 1e6 + 10;
//const int maxs = 9;
const int inf = 1e9 + 10;
const int mod = 998244353;
int n, m, b[maxn], p[maxn], d[maxn];
vector<int> G[maxn];
signed main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> b[i] >> p[i];
G[b[i]].pb(p[i]);
}
for (int i = 0; i < n; i++) {
d[i] = inf;
}
set<pii> se;
d[b[1]] = 0;
se.insert({0, b[1]});
while (!se.empty()) {
auto tmp = *se.begin();
se.erase(tmp);
auto [d_, v] = tmp;
for (int k : G[v]) {
int w;
w = 1;
for (int u = v - k; u >= 0; u -= k) {
if (d[u] > d[v] + w) {
se.erase({d[u], u});
d[u] = d[v] + w;
se.insert({d[u], u});
}
w++;
}
w = 1;
for (int u = v + k; u < n; u += k) {
if (d[u] > d[v] + w) {
se.erase({d[u], u});
d[u] = d[v] + w;
se.insert({d[u], u});
}
w++;
}
}
}
if (d[b[2]] >= inf)
d[b[2]] = -1;
cout << d[b[2]] << '\n';
}
