#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 3e4+5;
const int half = 173;
int n, m;
int dist[maxn*180*2];
vector< ii > adj[maxn];
bool ok(int x)
{
return 0<= x && x< n;
}
int N;
priority_queue< pair<int, int> > q;
int conv(int u, int md, int isleft)
{
if(isleft) return (half+1)*n+(md-1)*n+u;
return md*n+u;
}
void bfs(int s)
{
for(int i = 0; i< N; i++) dist[i] = 1e9;
dist[s] = 0; q.push({0, s});
while(!q.empty())
{
auto kk = q.top(); q.pop();
int u = kk.Y, d = -kk.X;
// printf("%d\n", u);
if(d> dist[u]) continue;
if(u< n)
{
for(auto k2 : adj[u])
{
int v = k2.X, w = k2.Y;
if(dist[v]> dist[u]+w)
{
dist[v] = dist[u]+w;
q.push({-dist[v], v});
}
}
}
if(u>= n)
{
bool isleft = false;
int tmp;
if(u< (half+1)*n)
{
isleft = false;
tmp = u-n;
}
else
{
isleft = true;
tmp = u-(half+1)*n;
}
int md = tmp/n+1;
int sub = tmp%n;
// assert(conv(sub, md, isleft) == u);
if(isleft && ok(sub-md))
{
int nxt = conv(sub-md, md, isleft);
if(dist[nxt]> dist[u]+1)
{
dist[nxt] = dist[u]+1;
q.push({-dist[nxt], nxt});
}
if(dist[sub-md]> dist[u]+1)
{
dist[sub-md] = dist[u]+1;
q.push({-dist[sub-md], sub-md});
}
}
if(!isleft && ok(sub+md))
{
int nxt = conv(sub+md, md, isleft);
if(dist[nxt]> dist[u]+1)
{
dist[nxt] = dist[u]+1;
q.push({-dist[nxt], nxt});
}
if(dist[sub+md]> dist[u]+1)
{
dist[sub+md] = dist[u]+1;
q.push({-dist[sub+md], sub+md});
}
}
}
}
}
int hom[maxn], mana[maxn];
int main()
{
scanf("%d %d", &n, &m);
N = conv(n-1, half, 1);
for(int i = 0; i< m; i++)
{
scanf("%d %d", &hom[i], &mana[i]);
}
// printf("okay\n");
for(int i = 0; i< m; i++)
{
int pw = mana[i];
if(pw> half)
{
int cur = hom[i]+pw;
while(cur< n)
{
adj[hom[i]].pb({cur, abs(cur-hom[i])/pw});
cur += pw;
}
cur = hom[i]-pw;
while(cur>= 0)
{
adj[hom[i]].pb({cur, abs(cur-hom[i])/pw});
cur -= pw;
}
}
else
{
int x = hom[i];
adj[x].pb({conv(x, pw, 0), 0});
adj[x].pb({conv(x, pw, 1), 0});
}
}
bfs(hom[0]);
if(dist[hom[1]] == 1e9) printf("-1\n");
else printf("%d\n", dist[hom[1]]);
}
