#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define len(s) (ll)s.size()
const ll I = 2e5 + 9;
const ll Z = 998244353;
using namespace std;
int n, m;
namespace subfull
{
vector<pair<pair<int, int>, int>> adj[5009][230];
priority_queue<pair<ll, pair<int, int>>> pq;
bool check[2007][2008];
ll dis[50008][230];
void addEd(ll u, ll xu, ll v, ll xv, ll w)
{
adj[u][xu].push_back({{v, xv}, w});
}
void solve()
{
ll sav, root;
for (ll i = 1; i <= m; i++)
{
ll pos, power;
cin >> pos >> power;
if (i == 2)
sav = pos;
if (i == 1)
root = pos;
if (power >= sqrt(n))
{
for (ll j = pos - power, w = 1; j >= 0; j -= power, w++)
adj[pos][0].push_back({{j, 0}, w});
for (ll j = pos + power, w = 1; j < n; j += power, w++)
adj[pos][0].push_back({{j, 0}, w});
continue;
}
addEd(pos, power, pos, 0, 0);
addEd(pos, 0, pos, power, 0);
if (pos - power >= 0)
{
addEd(pos, power, pos - power, 0, 1);
addEd(pos, power, pos - power, power, 1);
}
if (pos + power < n)
{
addEd(pos, power, pos + power, power, 1);
addEd(pos, power, pos + power, 0, 1);
}
}
memset(dis, 10, sizeof dis);
dis[root][0] = 0;
pq.push({0, {root, 0}});
ll rs = dis[1][1];
while (!pq.empty())
{
ll af = pq.top().se.fi, as = pq.top().se.se;
pq.pop();
if (check[af][as])
continue;
check[af][as] = true;
if (af == sav)
rs = min(rs, dis[af][as]);
if (as != 0)
{
if (af + as < n && dis[af + as][as] > dis[af][as] + 1)
{
dis[af + as][as] = dis[af][as] + 1;
pq.push({-dis[af + as][as], {af + as, as}});
}
if (af - as >= 0 && dis[af - as][as] > dis[af][as] + 1)
{
dis[af - as][as] = dis[af][as] + 1;
pq.push({-dis[af - as][as], {af - as, as}});
}
if (dis[af][0] > dis[af][as])
{
dis[af][0] = dis[af][as];
pq.push({-dis[af][0], {af, 0}});
}
}
for (auto z : adj[af][as])
{
if (dis[z.fi.fi][z.fi.se] > dis[af][as] + z.se)
{
dis[z.fi.fi][z.fi.se] = dis[af][as] + z.se;
pq.push({-dis[z.fi.fi][z.fi.se], {z.fi.fi, z.fi.se}});
}
}
}
cout << (rs < 1000000000 ? rs : -1);
}
}
int main()
{
#define TN "sky"
if (fopen(TN ".inp", "r"))
{
freopen(TN ".inp", "r", stdin);
freopen(TN ".out", "w", stdout);
}
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
subfull::solve();
return 0;
}
