#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 3e4+4, mod = 1e9 + 7, inf = 1e17, SQ = 450, LG = 20;
typedef pair<int, int> pii;
int n, m, B[maxn], P[maxn];
ll dis[maxn];
vector<int> mv[maxn];
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1 ; i <= m ; i ++) {
cin >> B[i] >> P[i];
mv[B[i]].pb(P[i]);
}
for (int i = 0 ; i < n ; i ++) {
sort(mv[i].begin(), mv[i].end());
mv[i].resize(unique(mv[i].begin(), mv[i].end()) - mv[i].begin());
dis[i] = inf;
}
priority_queue<pii, vector<pii>, greater<pii>> q;
dis[B[1]] = 0;
q.push({0, B[1]});
while (q.size()) {
auto [d, v] = q.top(); q.pop();
if (d > dis[v]) continue;
for (int x : mv[v]) {
for (int u = v + x, k = 1 ; u < n ; u += x, k ++) {
if (dis[u] > dis[v] + k) {
dis[u] = dis[v] + k;
q.push({dis[u], u});
}
}
for (int u = v - x, k = 1 ; u >= 0 ; u -= x, k ++) {
if (dis[u] > dis[v] + k) {
dis[u] = dis[v] + k;
q.push({dis[u], u});
}
}
}
}
cout << (dis[B[2]] == inf ? -1 : dis[B[2]]) << nl;
}
