#include <bits/stdc++.h>
using namespace std;
const int N = 30005, B = 175, oo = 1e9 + 7;
bool mini(int &X, int Y) {
return (X > Y) ? X = Y, true : false;
}
int n, m, b[N], p[N];
vector<array<int, 3>> adj[N][B + 5]; int d[N][B + 5];
const int D = N * 50; vector<array<int, 2>> pq[D];
void solve(void) {
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> b[i] >> p[i];
if (p[i] > B) {
for (int pos = b[i] + p[i], w = 1; pos < n; pos += p[i], w++) {
adj[b[i]][0].push_back({pos, 0, w});
}
for (int pos = b[i] - p[i], w = 1; pos >= 0; pos -= p[i], w++) {
adj[b[i]][0].push_back({pos, 0, w});
}
} else {
adj[b[i]][0].push_back({b[i], p[i], 0});
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j <= B; j++) {
d[i][j] = oo;
}
}
d[b[0]][p[0]] = 0;
pq[0].push_back({b[0], p[0]});
for (int di = 0; di < D; di++) {
while (pq[di].size()) {
auto t = pq[di].back();
int i = t[0], po = t[1];
pq[di].pop_back();
if (di != d[i][po]) continue;
if (po) {
if (i + po < n && mini(d[i + po][po], di + 1)) {
pq[d[i + po][po]].push_back({i + po, po});
}
if (i - po >= 0 && mini(d[i - po][po], di + 1)) {
pq[d[i - po][po]].push_back({i - po, po});
}
if (mini(d[i][0], di)) {
pq[d[i][0]].push_back({i, 0});
}
}
for (auto V: adj[i][po]) {
int i_ = V[0], po_ = V[1], w = V[2];
if (mini(d[i_][po_], di + w)) {
pq[d[i_][po_]].push_back({i_, po_});
}
}
}
}
int ans = oo;
for (int po = 0; po <= B; po++) {
mini(ans, d[b[1]][po]);
}
if (ans == oo) ans = -1;
cout << ans;
}
signed main(void) {
ios::sync_with_stdio(false); cin.tie(nullptr);
solve();
return 0;
}
