#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 5;
int n, m, dis[N];
vector<pair<int, int>> adj[N];
set<int> doge[N];
int s = -1, t = -1;
signed main() {
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
cin >> n >> m;
memset(dis, 0x3f, sizeof dis);
for (int p, d; m --; ) {
cin >> p >> d;
if (s == -1) s = p;
else if (t == -1) t = p;
doge[p].insert(d);
}
for (int i = 0; i < n; i++) {
for (auto d : doge[i]) {
for (int j = i + d, w = 1; j < n; j += d, w++) {
// cout << i << ' ' << j << ' ' << w << '\n';
adj[i].emplace_back(j, w);
if (doge[j].count(d)) break ;
}
for (int j = i - d, w = 1; j >= 0; j -= d, w++) {
// cout << i << ' ' << j << ' ' << w << '\n';
adj[i].emplace_back(j, w);
if (doge[j].count(d)) break ;
}
}
}
priority_queue<pair<int, int>> pq;
pq.emplace(dis[s] = 0, s);
while (!pq.empty()) {
int d = -pq.top().first, u = pq.top().second; pq.pop();
if (d != dis[u]) continue ;
if (u == t)
return cout << d, 0;
for (auto [v, w] : adj[u]) {
if (dis[v] > d + w)
pq.emplace(-(dis[v] = d + w), v);
}
}
cout << -1;
}
