#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];
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;
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
pq.push({0, b[0], p[0]});
while (pq.size()) {
auto t = pq.top();
int di = t[0], i = t[1], po = t[2];
pq.pop();
if (di != d[i][po]) continue;
if (po) {
if (i + po < n && mini(d[i + po][po], di + 1)) {
pq.push({d[i + po][po], i + po, po});
}
if (i - po >= 0 && mini(d[i - po][po], di + 1)) {
pq.push({d[i - po][po], i - po, po});
}
if (mini(d[i][0], di)) {
pq.push({d[i][0], 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.push({d[i_][po_], 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;
}
