#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
const int MAX = 1e9;
const int mxN = 3e4;
const int SQRT = 100;
pii doge[mxN];
vector<pii> adj[mxN * (SQRT + 1)];
int dist[mxN * (SQRT + 1)];
void AddEdge(int u, int v, int w) {
adj[u].pb({v, w});
}
int n;
void init() {
for (int i = 0; i < mxN * (SQRT + 1); i++) {
adj[i].clear();
dist[i] = MAX;
}
// dummy nodes for P_i < SQRT
for (int diff = 1; diff <= min(n, SQRT); diff++) {
for (int i = 0; i < n; i++) {
AddEdge(diff * mxN + i, i, 0);
}
for (int i = diff; i < n; i++) {
int u = diff * mxN + (i - diff);
int v = diff * mxN + i;
AddEdge(u, v, 1);
AddEdge(v, u, 1);
}
}
}
void solve() {
int m;
cin >> n >> m;
init();
for (int i = 0; i < m; i++) {
cin >> doge[i].ff >> doge[i].ss;
if (doge[i].ss <= SQRT) {
// connect to dummy nodes
AddEdge(doge[i].ff, doge[i].ss * mxN + doge[i].ff, 0);
} else {
// connect actual edges
for (int step = 1; doge[i].ff + doge[i].ss * step < n; step++) {
AddEdge(doge[i].ff, doge[i].ff + doge[i].ss * step, step);
}
for (int step = 1; doge[i].ff - doge[i].ss * step >= 0; step++) {
AddEdge(doge[i].ff, doge[i].ff - doge[i].ss * step, step);
}
}
}
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, doge[0].ff});
dist[doge[0].ff] = 0;
while (!pq.empty()) {
pii cur = pq.top();
pq.pop();
if (dist[cur.ss] > cur.ff) continue;
for (pii &v : adj[cur.ss]) {
if (cur.ff + v.ss >= dist[v.ff]) continue;
dist[v.ff] = cur.ff + v.ss;
pq.push({dist[v.ff], v.ff});
}
}
int ans = dist[doge[1].ff];
cout << (ans >= MAX ? -1 : ans) << endl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
solve();
}
