// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int MOD = 1e9 + 7;
ll binpow(ll a, ll p, int mod = MOD) {
ll res = 1;
while (p) {
if (p & 1) {
(res *= a) %= mod;
}
p >>= 1;
(a *= a) %= mod;
}
return res;
}
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
const int N = 30005;
const int M = 600;
int dist[N][M + 1];
set<int> doges[N];
void solve() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
fill(dist[i], dist[i] + M + 1, 1e9);
}
pair<int, int> start;
int finish;
for (int i = 0; i < m; i++) {
int b, p;
cin >> b >> p;
doges[b].insert(p);
if (i == 0) {
start = {b, M};
dist[b][M] = 0;
}
if (i == 1) {
finish = b;
}
}
set<pair<int, pair<int, int>>> setik;
setik.insert({0, start});
while (!setik.empty()) {
int v, p;
tie(v, p) = setik.begin()->second;
setik.erase(setik.begin());
if (p == M) {
for (int doge : doges[v]) {
if (doge < M) {
if (dist[v][p] < dist[v][doge]) {
setik.erase({dist[v][doge], {v, doge}});
dist[v][doge] = dist[v][p];
setik.insert({dist[v][doge], {v, doge}});
}
} else {
for (int i = v % doge; i < n; i += doge) {
if (dist[v][p] + abs(v - i) / doge < dist[v][M]) {
setik.erase({dist[v][M], {v, M}});
dist[v][M] = dist[v][p] + abs(v - i) / doge;
setik.insert({dist[v][M], {v, M}});
}
}
}
}
continue;
}
if (v + p < n && dist[v][p] + 1 < dist[v + p][p]) {
setik.erase({dist[v + p][p], {v + p, p}});
dist[v + p][p] = dist[v][p] + 1;
setik.insert({dist[v + p][p], {v + p, p}});
}
if (v - p >= 0 && dist[v][p] + 1 < dist[v - p][p]) {
setik.erase({dist[v - p][p], {v - p, p}});
dist[v - p][p] = dist[v][p] + 1;
setik.insert({dist[v - p][p], {v - p, p}});
}
if (dist[v][p] < dist[v][M]) {
setik.erase({dist[v][M], {v, M}});
dist[v][M] = dist[v][p];
setik.insert({dist[v][M], {v, M}});
}
}
int ans = *min_element(dist[finish], dist[finish] + M + 1);
if (ans == 1e9) ans = -1;
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
for (int tc = 1; tc <= T; tc++) {
// cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
