#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*180*2];
bool ok(int x)
{
return 0<= x && x< n;
}
int N;
priority_queue< pair<int, int> > q;
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;
if(d> dist[u]) continue;
for(auto k2 : adj[u])
{
int v = k2.X, w = k2.Y;
// printf("(%d, %d)\n", v, w);
if(dist[v]> dist[u]+w)
{
dist[v] = dist[u]+w;
q.push({-dist[v], v});
}
}
}
}
int hom[maxn], mana[maxn];
int conv(int u, int md, int isleft)
{
if(isleft) return (half+1)*n+(md-1)*n+u;
return md*n+u;
}
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< n; i++)
{
for(int md = 1; md<= half; md++)
{
if(ok(i+md))
{
adj[conv(i, md, 0)].pb({i+md, 1});
adj[conv(i, md, 0)].pb({conv(i+md, md, 0), 1});
}
if(ok(i-md))
{
adj[conv(i, md, 1)].pb({i-md, 1});
adj[conv(i, md, 1)].pb({conv(i-md, md, 1), 1});
}
}
}
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]]);
}
