#include <bits/stdc++.h>
using namespace std;
/*
we run dijkstra
let B = 100
for all doges that have p >= b, just simulate the jumps
how do we deal with the "small" doges??
note that the answer is never more than 30000...
*/
const int SMALL = 100;
const int MAXN = 30000;
const int INF = 1e9;
int mintime[MAXN][SMALL + 1];
int dist[MAXN];
vector<int> doges[MAXN];
priority_queue<pair<int, int>> pq;
int main() {
int n; cin >> n;
int m; cin >> m;
for (int i = 0; i < n; i ++)
for (int j = 1; j <= SMALL; j ++)
mintime[i][j] = INF;
for (int i = 0; i < n; i ++)
dist[i] = INF;
int startnode = -1, target = -1;
for (int i = 0; i < m; i ++) {
int b, p; cin >> b >> p;
if (i == 0)
startnode = b;
else if (i == 1)
target = b;
doges[b].push_back(p);
}
if (startnode == target) {
cout << 0 << endl; return 0;
}
pq.push({0, startnode});
dist[startnode] = 0;
while (pq.size()) {
pair<int, int> xx = pq.top(); pq.pop();
int t = -xx.first;
int curnode = xx.second;
if (dist[curnode] != t)
continue;
for (auto doge : doges[curnode]) {
// big doge
if (doge > SMALL) {
int extratime = 0;
for (int j = curnode - doge; j >= 0; j -= doge) {
extratime ++;
if (dist[j] > extratime + t) {
dist[j] = extratime + t;
pq.push({-dist[j], j});
}
}
extratime = 0;
for (int j = curnode + doge; j < n; j += doge) {
extratime ++;
if (dist[j] > extratime + t) {
dist[j] = extratime + t;
pq.push({-dist[j], j});
}
}
}
// small doge
else {
// ignore entirely
if (mintime[curnode][doge] <= t)
continue;
mintime[curnode][doge] = t;
int extratime = 0;
for (int j = curnode - doge; j >= 0; j -= doge) {
extratime ++;
// stop
if (mintime[j][doge] <= t + extratime)
break;
mintime[j][doge] = t + extratime;
if (dist[j] > extratime + t) {
dist[j] = extratime + t;
pq.push({-dist[j], j});
}
}
extratime = 0;
for (int j = curnode + doge; j < n; j += doge) {
extratime ++;
// stop
if (mintime[j][doge] <= t + extratime)
break;
mintime[j][doge] = t + extratime;
if (dist[j] > extratime + t) {
dist[j] = extratime + t;
pq.push({-dist[j], j});
}
}
}
}
if (curnode == target) {
break;
}
}
if (dist[target] == INF) {
cout << -1 << endl;
} else cout << dist[target] << endl;
return 0;
}
