#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, bool 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 <= 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
int cur;
cur = doge[i].ff;
while (cur + doge[i].ss < n) {
AddEdge(cur, cur + doge[i].ss, 1);
cur += doge[i].ss;
}
cur = doge[i].ff;
while (cur - doge[i].ss >= 0) {
AddEdge(cur, cur - doge[i].ss, 1);
cur -= doge[i].ss;
}
}
}
// 0-1 BFS
deque<pii> dq;
dq.push_back({doge[0].ff, 0});
dist[doge[0].ff] = 0;
while (!dq.empty()) {
pii cur = dq.front();
dq.pop_front();
for (pii &v : adj[cur.ff]) {
if (cur.ss + v.ss >= dist[v.ff]) continue;
dist[v.ff] = cur.ss + v.ss;
if (!v.ss) dq.push_front({v.ff, dist[v.ff]});
else dq.push_back({v.ff, dist[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();
}
