#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 30010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1 << j))
#define onbit(i, j) (i | (1 << j))
#define vi vector<int>
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
using namespace std;
const int nsqrt = 175;
int n, m;
pii a[maxn];
int d[maxn][nsqrt + 1];
vector<array<int, 3>> ke[maxn][nsqrt + 1];
vi adj[maxn];
pii par[maxn][nsqrt + 1];
void dij(pii inp)
{
fo(i, 0, maxn - 1) fo(j, 0, nsqrt - 1) d[i][j] = inf;
d[inp.fi][inp.se] = 0;
priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> q;
q.push({0, inp});
while (q.size())
{
int du = q.top().fi;
int i = q.top().se.fi;
int j = q.top().se.se;
q.pop();
if (du != d[i][j])
continue;
for (auto [i1, j1, w] : ke[i][j])
{
if (d[i1][j1] > du + w)
{
par[i1][j1] = {i,j};
d[i1][j1] = du + w;
q.push({d[i1][j1], {i1, j1}});
}
}
if (i + j <= n and d[i + j][j] > du + 1)
{
par[i + j][j] = {i,j};
d[i + j][j] = du + 1;
q.push({du + 1, {i + j, j}});
}
if (i - j > 0 and d[i - j][j] > du + 1)
{
par[i - j][j] = {i,j};
d[i - j][j] = du + 1;
q.push({du + 1, {i - j, j}});
}
if (d[i][0] > du)
{
par[i][0] = {i,j};
d[i][0] = du;
q.push({du, {i, 0}});
}
}
}
vi save1[maxn];
bool used[maxn];
int s,t;
main()
{
#define name "TASK"
if (fopen(name ".inp", "r"))
{
freopen(name ".inp", "r", stdin);
freopen(name ".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
vi v;
fo(i, 1, m)
{
cin >> a[i].fi >> a[i].se;
a[i].fi++;
if (a[i].se <= nsqrt and a[i].se)
ke[a[i].fi][0].push_back({a[i].fi,a[i].se,0});
else
save1[a[i].fi].pb(a[i].se);
v.pb(a[i].fi);
}
s = a[1].fi,t = a[2].fi;
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
// for (int it : v) for (int u : adj[it]) if(u) ke[it][0].push_back({it, u, 0});
for (int it : v)
{
if (save1[it].empty())
continue;
for (int i : save1[it])
if (!used[i] and i > 0)
{
used[i] = 1;
int pos = it;
while (pos - i > 0)
{
ke[it][0].push_back({pos - i, 0, (it - pos) / i});
pos -= i;
}
pos = it;
while (pos + i <= n)
{
ke[it][0].push_back({pos + i, 0, (pos - it) / i});
pos += i;
}
}
for (int i : save1[it])
used[i] = 0;
}
// for(auto [i,j,v] : ke[833][0]) cout << i << ' ' << j << ' ' << v << "\n";
dij({s, 0});
// cout << s << ' ' << t << "\n";
// cout << par[t][0].fi << ' ' << par[t][0].se << "\n";
// cout << par[901][28].fi << ' ' << par[901][28].se << "\n";
// cout << par[929][28].fi << ' ' << par[929][28].se << "\n";
// cout << par[957][28].fi << ' ' << par[957][28].se << "\n";
// cout << par[985][28].fi << ' ' << par[985][28].se << "\n";
// cout << par[985][0].fi << ' ' << par[985][0].se << "\n";
// cout << par[985][40].fi << ' ' << par[985][40].se << "\n";
// cout << par[1025][40].fi << ' ' << par[1025][40].se << "\n";
// cout << par[1025][0].fi << ' ' << par[1025][0].se << "\n";
// cout << par[1025][96].fi << ' ' << par[1025][96].se << "\n";
// cout << par[929][96].fi << ' ' << par[929][96].se << "\n";
cout << (d[t][0] == inf ? -1 : d[t][0]);
}
