//{ <defines>
#ifndef _LOCAL
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#endif
#include <bits/stdc++.h>
using namespace std;
#define fr(i, n) for(int i = 0; i < n; ++i)
#define fo(n) fr(i, n)
#define re return
#define ef else if
#define ifn(x) if(!(x))
#define _ << ' ' <<
#define ft first
#define sd second
#define ve vector
#define pb push_back
#define eb emplace_back
#define sz(x) int(x.size())
#define pw(x) (1 << (x))
#define PW(x) (1ll << (x))
#define bnd(x) x.begin(), x.end()
#define clr(x, y) memset(x, y, sizeof x)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef ve<int> vi;
const int oo = 2e9;
const ll OO = 4e18;
//const ld pi = arg(complex<ld>(-1, 0));
//const ld pi2 = pi + pi;
const int md = 0x3b800001;
const int MD = 1e9 + 7;
inline ll time() {re chrono :: system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
mt19937_64 RND(time());
template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}
//} </defines>
const int N = 1e5 + 5;
const int D = 1e9;
int n, m, st, fn, d[N];
vi g[N];
bool mk[N];
inline int mn(int x, int y) {re d[x] < d[y] ? x : y;}
struct tree {
int v[N << 2];
int p[N];
void assign(int l, int r, int u) {
assert(u < (N << 2));
if(l == r) {
p[l] = u >> 1;
v[u] = r;
} else {
int m = (l + r) >> 1;
assign(l, m, u + u);
assign(m + 1, r, u + u + 1);
v[u] = mn(v[u + u], v[u + u + 1]);
}
}
tree() {
assign(0, n - 1, 1);
}
inline void upd(int i) {
for(i = p[i]; i; i >>= 1)
v[i] = mn(v[i + i], v[i + i + 1]);
}
};
void solve() {
cin >> n >> m;
fo(m) {
int b, p;
cin >> b >> p;
if(i == 0) st = b;
if(i == 1) fn = b;
g[b].pb(p);
}
fo(n) d[i] = D;
d[st] = 0;
fo(n) sort(bnd(g[i]));
tree *t = new tree();
for(;;) {
int v = t -> v[1];
if(mk[v]) break;
if(v == fn) re void(cout << d[fn] << endl);
int pr = -1;
for(int p : g[v]) if(p != pr) {
pr = p;
for(int c = -p; c <= p; c += p + p) {
for(int w = d[v] + 1, u = v + c; u >= 0 && u < n; ++w, u += c) {
if(mk[u]) continue;
if(w < d[u]) {
d[u] = w;
t -> upd(u);
}
}
}
}
d[v] = D; t -> upd(v); mk[v] = true;
}
cout << -1 << endl;
}
/*
5 3
0 2
1 1
4 1
*/
int main() {
solve();
}
