#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> b(m), p(m);
vector<vector<int>> doge(n + 1);
for (int i = 0; i < m; i++) {
cin >> b[i] >> p[i];
doge[b[i]].emplace_back(i);
}
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
pq.push({0, {b[0], 0}});
vector<vector<int>> dist(n, vector<int>(200, 1e9));
dist[b[0]][0] = 0;
int limit = (int)sqrt(n);
int res = 1e9;
while (!pq.empty()) {
pair<int, pair<int, int>> cur = pq.top();
pq.pop();
int du = cur.first;
int u = cur.second.first;
if (u == b[1]) {
res = min(res, du);
}
int pu = cur.second.second;
if (pu == 0) {
for (int id : doge[u]) {
if (p[id] <= limit) { // nsqrt(n)
if (dist[u][p[id]] > du) {
dist[u][p[id]] = du;
pq.push({du, {u, p[id]}});
}
} else { // msqrt(n)
int pv = p[id];
for (int j = 1; u - j * pv >= 0; j++) {
int v = u - j * pv;
int dv = du + j;
if (dist[v][0] > dv) {
dist[v][0] = dv;
pq.push({dv, {v, 0}});
}
}
for (int j = 1; u + j * pv < n; j++) {
int v = u + j * pv;
int dv = du + j;
if (dist[v][0] > dv) {
dist[v][0] = dv;
pq.push({dv, {v, 0}});
}
}
}
}
} else {
if (dist[u][0] > du) { // nsqrt(n)
dist[u][0] = du;
pq.push({dist[u][0], {u, 0}});
}
// 2nsqrt(n)
if (u + pu < n && dist[u + pu][pu] > dist[u][pu] + 1) {
int dv = dist[u][pu] + 1;
int v = u + pu;
dist[v][pu] = dist[u][pu] + 1;
pq.push({dv, {v, pu}});
}
if (u - pu >= 0 && dist[u - pu][pu] > dist[u][pu] + 1) {
int dv = dist[u][pu] + 1;
int v = u - pu;
dist[v][pu] = dist[u][pu] + 1;
pq.push({dv, {v, pu}});
}
}
}
cout << (res == 1e9 ? -1 : res);
return 0;
}
