#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mxN = 30'000;
set<int> l[mxN], init[mxN];
vector<int> all[mxN];
vector<int> dist[mxN];
bool vis[mxN];
int idx(int i, int j) {
return lower_bound(all[i].begin(), all[i].end(), j) - all[i].begin();
}
void testCase() {
int n, m;
cin >> n >> m;
vector<int> v;
while (m--) {
int b, p;
cin >> b >> p;
v.push_back(b);
init[b].insert(p);
l[b % p].insert(p);
}
for (int i = 0; i < n; i++) {
for (int j : l[i]) {
if (i + j < n) l[i + j].insert(j);
}
all[i] = vector<int> (l[i].begin(), l[i].end());
dist[i].assign(all[i].size(), 1e9);
}
deque<pair<int, int>> q;
for (auto p : init[v[0]]) {
q.push_back({v[0], p});
dist[v[0]][idx(0, p)] = 0;
}
while (!q.empty()) {
auto [u, p] = q.front();
// debug(u, p, dist[u][idx(u, p)]);
q.pop_front();
if (u + p < n && dist[u + p][idx(u + p, p)] == 1e9) {
dist[u + p][idx(u + p, p)] = dist[u][idx(u, p)] + 1;
q.push_front({u + p, p});
}
if (u - p >= 0 && dist[u - p][idx(u - p, p)] == 1e9) {
dist[u - p][idx(u - p, p)] = dist[u][idx(u, p)] + 1;
q.push_front({u - p, p});
}
if (vis[u]) continue;
int j = idx(u, p);
for (int pp : init[u]) {
if (dist[u][idx(u, pp)] == 1e9) {
dist[u][idx(u, pp)] = dist[u][j];
q.push_back({u, pp});
}
}
vis[u] = true;
}
int ans = *min_element(dist[v[1]].begin(), dist[v[1]].end());
cout << (ans == 1e9 ? -1 : ans) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
testCase();
return 0;
}
