#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
template <class X, class Y>
bool minimize(X &x, Y y) {
if (x > y) return x = y, true;
else return false;
}
int n, m;
const ll INF = (ll) 1e18 + 7;
#define ii pair <long long, int>
#define MAX 50'005
vector <ii> adj[MAX + 2];
int b[MAX + 2], p[MAX + 2];
ll dist[MAX + 2];
set <int> jump[MAX + 2], go[MAX + 2];
void Dijkstra(int s) {
priority_queue <ii, vector <ii>, greater <ii>> q;
FOR(i, 1, n) dist[i] = INF;
dist[s] = 0;
q.push({0, s});
while (!q.empty()) {
ll cost = q.top().first;
int u = q.top().second;
q.pop();
if (cost > dist[u]) continue;
if (u == b[2]) return void(cout << cost);
for (auto it : adj[u]) {
int v = it.first, w = it.second;
if (minimize(dist[v], dist[u] + w)) {
q.push({dist[v], v});
}
}
}
cout << -1;
}
void add_edge(int u, int v, int w) {
adj[u].push_back({v, w});
}
bool used[MAX + 2];
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define task "sky"
if (fopen(task".inp","r")) {
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin >> n >> m;
memset(used, false, sizeof(used));
FOR(i, 1, m) {
cin >> b[i] >> p[i];
++b[i];
used[b[i]] = true;
jump[b[i]].insert(p[i]);
}
FOR(i, 1, n) {
if (!used[i]) continue;
for (int x : jump[i]) {
int j = x + i, cur = 1;
while (j <= n) {
if (used[j]) {
add_edge(i, j, cur);
if (go[j].find(x) != go[j].end()) break;
else go[j].insert(x);
}
j += x;
++cur;
}
}
}
FOR(i, 1, n) {
if (!used[i]) continue;
for (int x : jump[i]) {
int j = i - x, cur = 1;
while (j >= 1) {
if (used[j]) {
add_edge(i, j, cur);
if (go[j].find(x) != go[j].end()) break;
else go[j].insert(x);
}
j -= x;
++cur;
}
}
}
Dijkstra(b[1]);
return 0;
}
