#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
using ll = long long;
const int inf = 1e9 + 5;
bool chmin(int &a, const int &b) {
return a > b ? a = b, true : false;
}
const int B = 180;
void solve() {
int n, m; cin >> n >> m;
vector<int> b(m), p(m);
vector adj(n, vector(B, vector<array<int, 3>>()));
for(int i = 0; i < m; i++) {
cin >> b[i] >> p[i];
if(p[i] < B) {
adj[b[i]][0].push_back({b[i], p[i], 0});
} else {
for(int j = b[i], cur = 0; j < n; j += p[i], cur++) {
adj[b[i]][0].push_back({j, 0, cur});
}
for(int j = b[i], cur = 0; j >= 0; j -= p[i], cur++) {
adj[b[i]][0].push_back({j, 0, cur});
}
}
}
for(int i = 0; i < n; i++) {
for(int j = 1; j < B; j++) {
adj[i][j].push_back({i, 0, 0});
if(i + j < n) adj[i][j].push_back({i + j, j, 1});
if(i - j >= 0) adj[i][j].push_back({i - j, j, 1});
}
}
// (position, 0) = (position)
vector d(n, vector(B, inf));
d[b[0]][0] = 0;
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
pq.push({0, b[0], 0});
while(!pq.empty()) {
auto [d_v, pos, pw] = pq.top();
pq.pop();
// cout << d_v << ' ' << pos << ' ' << pw << nl;
if(d_v != d[pos][pw]) continue;
for(auto [npos, npw, w] : adj[pos][pw]) {
if(chmin(d[npos][npw], d[pos][pw] + w)) {
pq.push({d[npos][npw], npos, npw});
}
}
}
int ans = d[b[1]][0];
if(ans == inf) ans = -1;
cout << ans << nl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
