#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>
const ll mod = 1e9 + 7;
const ll MAXN = 3 * 1e3 + 5;
const ll oo = 1e10;
const ll base = 320;
int n, m, b[MAXN], p[MAXN], f[MAXN][base + 5];
vector<tuple<int, int, int>> adj[MAXN][base + 5];
void disjktra()
{
priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> q;
FOR(i, 0, n + 5)
{
FOR(j, 0, base + 5)
{
f[i][j] = oo;
}
}
f[0][0] = 0;
q.push({0, {0, 0}});
while (q.size())
{
int c = q.top().fi;
auto [nha, j] = q.top().se;
q.pop();
if (c > f[nha][j])
continue;
for (auto [dnha, dj, w] : adj[nha][j])
{
if (f[dnha][dj] > f[nha][j] + w)
{
f[dnha][dj] = f[nha][j] + w;
q.push({f[dnha][dj], {dnha, dj}});
}
}
if (f[nha][0] > f[nha][j])
{
f[nha][0] = f[nha][j];
q.push({f[nha][0], {nha, 0}});
}
if (j != 0)
{
for (auto k = -1; k <= 1; k += 2)
{
if (nha + j * k >= 0 && nha + j * k < n)
{
int dnha = nha + j * k, dj = j, w = 1;
if (f[dnha][dj] > f[nha][j] + w)
{
f[dnha][dj] = f[nha][j] + w;
q.push({f[dnha][dj], {dnha, dj}});
}
}
}
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
if (fopen(".INP", "r"))
{
freopen(".INP", "r", stdin);
freopen(".OUT", "w", stdout);
}
cin >> n >> m;
FOR(i, 1, m)
{
cin >> b[i] >> p[i];
if (p[i] > base)
{
for (int k = -1; k <= 1; k += 2)
{
for (int j = 1; (b[i] + p[i] * j * k < n) && (b[i] + p[i] * j * k >= 0); j++)
{
adj[b[i]][p[i]].push_back({b[i] + p[i] * j * k, 0, j});
}
}
}
else
{
adj[b[i]][0].push_back({b[i], p[i], 0});
}
}
disjktra();
if (f[1][0] == oo)
cout << -1;
else
cout << f[1][0];
return 0;
}
