#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
template <class A, class B> bool minimize(A &a, B b) { return a > b ? a = b, true : false; }
template <class A, class B> bool maximize(A &a, B b) { return a < b ? a = b, true : false; }
const int N = 3e4, B = 175, INF = 1e9;
int n, m;
int b[N], p[N], d[N][B];
vector<int> node[N];
void dijkstra() {
using T = tuple<int, int, int>;
priority_queue<T, vector<T>, greater<T>> pq;
memset(d, 0x3f, sizeof(d));
pq.push({d[b[0]][0] = 0, b[0], 0});
while (pq.size()) {
int c, u, p;
tie(c, u, p) = pq.top();
pq.pop();
if (d[u][p] != c) {
continue;
}
if (p == 0) {
for (int x : node[u]) {
if (x >= B) {
for (int v = u - x, cnt = 1; v >= 0; v -= x, ++cnt) {
if (minimize(d[v][0], c + cnt)) {
pq.push({d[v][0], v, 0});
}
}
for (int v = u + x, cnt = 1; v < n; v += x, ++cnt) {
if (minimize(d[v][0], c + cnt)) {
pq.push({d[v][0], v, 0});
}
}
} else if (minimize(d[u][x], c)) {
pq.push({d[u][x], u, x});
}
}
} else {
if (minimize(d[u][0], c)) {
pq.push({d[u][0], u, 0});
}
for (int i = 0; i < 2; ++i) {
int v = u + (i ? 1 : -1) * p;
if (0 <= v && v < n && minimize(d[v][p], c + 1)) {
pq.push({d[v][p], v, p});
}
}
}
}
}
void process() {
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> b[i] >> p[i];
node[b[i]].push_back(p[i]);
}
dijkstra();
cout << (d[b[1]][0] >= INF ? -1 : d[b[1]][0]);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
file("B");
// int t; cin >> t; while (t--)
process();
return 0;
}
