#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> LP;
#define N 30004
#define OO int(1e9)
#define mp make_pair
#define pb push_back
vector<P>v[N];
vector<int>g[N];
ll x, y, z, dis[N][303], n, m, res, r, st, en, w, po;
priority_queue<LP, vector<LP>, greater<LP> >q;
LP f;
bool can(int pos)
{
return pos >= 0 && pos < n;
}
inline void normal_node()
{
for (auto u : v[x])//normal edge
if (w + u.second < dis[u.first][0])
dis[u.first][0] = w + u.second, q.push(mp(dis[u.first][0], mp(u.first, 0)));
for (auto u : g[x])//power edge
if (dis[x][u]>w)
dis[x][u] = w, q.push(mp(w, mp(x, u)));
}
int main()
{
scanf("%d%d", &n, &m);
en = n;
r = sqrt(double(n));
for (int i = 0; i <= n; i++)
for (int j = 0; j <= r; j++)
dis[i][j] = OO;
for (int i = 0; i < m; i++)
{
scanf("%d%d", &x, &y);
if (i == 0)st = x;
else if (i == 1)en = x;
if (y>r)
{
for (int i = x - y, j = 1; i >= 0; i -= y, j++)v[x].pb(mp(i, j));
for (int i = x + y, j = 1; i < n; i += y, j++)v[x].pb(mp(i, j));
}
else
g[x].pb(y);
}
dis[st][0] = 0;
q.push(mp(0, mp(st, 0)));
for (auto u : g[st])
dis[st][u] = 0, q.push(mp(0, mp(st, u)));
while (!q.empty())
{
f = q.top();
q.pop();
x = f.second.first;
w = f.first;
po = f.second.second;
if (po != 0)//power node
{
y = x + po;
if (can(y) && w + 1 < dis[y][po])dis[y][po] = w + 1, q.push(mp(dis[y][po], mp(y, po)));
y = x - po;
if (can(y) && w + 1 < dis[y][po])dis[y][po] = w + 1, q.push(mp(dis[y][po], mp(y, po)));
if (dis[x][0] > w)dis[x][0] = w, q.push(mp(w, mp(x, 0)));
}
else
normal_node();
}
res = OO;
for (int i = 0; i <= r; i++)res = min(res, dis[en][i]);
if (res >= OO)res = -1;
printf("%d\n", res);
return 0;
}
