#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algos/debug.h"
#else
#define debug(...) 42;
#endif
#define all(x) (x).begin(), (x).end()
#define isz(x) (int)x.size()
const int sz = 30000 + 1, inf = 1e9;
array<int, 2> a[sz];
int ans = inf, d[sz];
vector<array<int, 2>> g[sz];
void run(int tc) {
int n, m;
cin >> n >> m;
set<int> s[n];
for (int i = 0; i < n; i++)
d[i] = inf;
for (int i = 0; i < m; i++) {
cin >> a[i][0] >> a[i][1];
s[a[i][0]].insert(a[i][1]);
}
for (int i = 0; i < n; i++) {
for (auto &k : s[i]) {
int steps = 1;
for (int pos = i + k; pos < n; pos += k) {
g[i].push_back({pos, steps});
if (s[pos].count(steps)) {
break;
}
steps++;
}
steps = 1;
for (int pos = i - k; pos >= 0; pos -= k) {
g[i].push_back({pos, steps});
if (s[pos].count(steps)) {
break;
}
steps++;
}
}
}
for (int i = 0; i < n; i++) {
debug(g[i]);
}
priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>>
pq;
pq.push({0, a[0][0]});
d[a[0][0]] = 0;
while (!pq.empty()) {
auto [d_v, v] = pq.top();
pq.pop();
if (d[v] != d_v)
continue;
for (auto &[u, w] : g[v]) {
if (d[u] > d_v + w) {
d[u] = d_v + w;
pq.push({d[u], u});
}
}
}
cout << (d[1] == inf ? -1 : d[1]) << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
for (int tc = 1; tc <= t; tc++)
run(tc);
}
