#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second
#define fastio ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(x) cerr << "[" << #x << "]: " << x << "\n";
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using pl = pair<ll, ll>;
constexpr ld PI = 4*atan((ld)1);
constexpr int MAX = 30069;
constexpr int SQ = 150;
constexpr int inf = 1e9 + 69;
int n, m;
int cost[MAX][SQ];
int b[MAX], p[MAX];
vector<int> adj[MAX];
int main()
{
fastio;
for (int i = 0; i < MAX; ++i)
for (int j = 0; j < SQ; ++j)
cost[i][j] = inf;
cin >> n >> m;
for (int i = 0; i < m; ++i)
{
cin >> b[i] >> p[i];
adj[b[i]].pb(p[i]);
}
const auto valid = [&](int pos) -> bool
{
return 0 <= pos && pos < n;
};
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq;
cost[b[0]][0] = 0;
if (p[0] < SQ)
{
cost[b[0]][p[0]] = 0;
pq.push({0, b[0], p[0]});
}
else
{
for (int i = b[0], ctr = 0; i >= 0; i -= p[0], ctr++)
cost[i][0] = ctr, pq.push({ctr, i, p[0]});
for (int i = b[0], ctr = 0; i < n; i += p[0], ctr++)
cost[i][0] = ctr, pq.push({ctr, i, p[0]});
}
while (!pq.empty())
{
auto [c, pos, mov] = pq.top();
pq.pop();
if (cost[pos][mov] < c)
continue;
if (mov < SQ)
{
if (valid(pos - mov) && cost[pos - mov][mov] > 1 + c)
{
cost[pos - mov][0] = min(cost[pos - mov][0], 1 + c);
cost[pos - mov][mov] = 1 + c;
pq.push({1 + c, pos - mov, mov});
}
if (valid(pos + mov) && cost[pos + mov][mov] > 1 + c)
{
cost[pos + mov][0] = min(cost[pos + mov][0], 1 + c);
cost[pos + mov][mov] = 1 + c;
pq.push({1 + c, pos + mov, mov});
}
}
for (int x : adj[pos])
{
if (x < SQ)
{
if (valid(pos - x) && cost[pos - x][x] > 1 + c)
{
cost[pos - x][0] = min(cost[pos - x][0], 1 + c);
cost[pos - x][x] = 1 + c;
pq.push({1 + c, pos - x, x});
}
if (valid(pos + x) && cost[pos + x][x] > 1 + c)
{
cost[pos + x][0] = min(cost[pos + x][0], 1 + c);
cost[pos + x][x] = 1 + c;
pq.push({1 + c, pos + x, x});
}
}
else
{
for (int i = pos, ctr = c; i >= 0; i -= x, ++ctr)
{
if (cost[i][0] > ctr)
cost[i][0] = ctr, pq.push({ctr, i, x});
}
for (int i = pos, ctr = c; i < n; i += x, ++ctr)
{
if (cost[i][0] > ctr)
cost[i][0] = ctr, pq.push({ctr, i, x});
}
}
}
adj[pos].clear();
}
// for (int i = 0; i < n; ++i)
// cerr << cost[i] << " \n"[i == n-1];
cout << (cost[b[1]][0] == inf ? -1 : cost[b[1]][0]) << '\n';
return 0;
}
