#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ww first
#define vv second
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
int N, M, b[30'050], p[30'050], sssp[30'050];
vvi dogesAt;
vvii adj;
void dijkstra(int source) {
memset(sssp, -1, sizeof sssp);
priority_queue<ii> pq;
pq.push({0, source});
while (!pq.empty()) {
ii u = pq.top(); pq.pop();
u.ww = -u.ww;
//cerr << "// pq.top() : {" << u.fi << ", " << u.se << "}\n";
if (sssp[u.vv] != -1 && sssp[u.vv] <= u.ww) continue;
sssp[u.vv] = u.ww;
for (ii v : adj[u.vv]) {
int newDis = u.ww + v.ww;
if (sssp[v.vv] == -1 || sssp[v.vv] > newDis) {
pq.push({-newDis, v.vv});
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
dogesAt.assign(N, vi());
adj.assign(M, vii());
for (int i = 0; i < M; i++) {
cin >> b[i] >> p[i];
dogesAt[b[i]].push_back(i);
}
for (int i = 0; i < M; i++) {
for (int j = b[i] + p[i], stepCount = 1; j < N; j += p[i], stepCount++) {
for (int d : dogesAt[j]) adj[i].push_back({stepCount, d});
}
for (int j = b[i] - p[i], stepCount = 1; j >= 0; j -= p[i], stepCount++) {
for (int d : dogesAt[j]) adj[i].push_back({stepCount, d});
}
}
//cerr << "// adj:-\n";
//for (int u = 0; u < M; u++) {
// cerr << "// " << u << " :";
// for (ii v : adj[u]) cerr << " {" << v.fi << ", " << v.se << "}";
// cerr << '\n';
//}
//cerr << '\n';
dijkstra(0);
//cerr << "// sssp :";
//for (int i = 0; i < M; i++) cerr << ' ' << sssp[i];
//cerr << '\n';
cout << sssp[1] << '\n';
}
