#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
constexpr int N = int(3E4);
constexpr int inf = int(1E9);
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> b(m);
vector<int> p(m);
for (int i = 0; i < m; ++i) {
cin >> b[i] >> p[i];
}
vector<vector<int>> by_p(N + 1);
for (int i = 0; i < m; ++i) {
by_p[p[i]].push_back(b[i] % p[i]);
}
for (auto& v : by_p) {
sort(v.begin(), v.end());
v.resize(distance(v.begin(), unique(v.begin(), v.end())));
}
vector<vector<int>> states(n);
for (int i = 1; i < N; ++i) {
if (by_p[i].empty()) {
continue;
}
for (int bias = 0; bias + by_p[i][0] < n; bias += i) {
for (int x : by_p[i]) {
if (bias + x >= n) {
break;
}
states[bias + x].push_back(i);
}
}
}
auto getId = [&states](int b, int p) {
return int(distance(states[b].begin(), lower_bound(states[b].begin(), states[b].end(), p)));
};
vector<vector<int>> can_get(n);
for (int i = 0; i < m; ++i) {
const int id = getId(b[i], p[i]);
can_get[b[i]].push_back(id);
}
vector<bool> first(n, true);
vector<vector<int>> d(n);
for (int i = 0; i < n; ++i) {
d[i].resize(states[i].size(), inf);
}
deque<pair<int, int>> dq;
{
const int id = getId(b[0], p[0]);
dq.emplace_back(b[0], id);
d[b[0]][id] = 0;
}
while (!dq.empty()) {
auto [x, y] = dq.front();
dq.pop_front();
if (x - states[x][y] >= 0) {
const int id = getId(x - states[x][y], states[x][y]);
if (d[x - states[x][y]][id] > d[x][y] + 1) {
d[x - states[x][y]][id] = d[x][y] + 1;
dq.emplace_back(x - states[x][y], id);
}
}
if (x + states[x][y] < n) {
const int id = getId(x + states[x][y], states[x][y]);
if (d[x + states[x][y]][id] > d[x][y] + 1) {
d[x + states[x][y]][id] = d[x][y] + 1;
dq.emplace_back(x + states[x][y], id);
}
}
if (first[x]) {
first[x] = false;
for (int id : can_get[x]) {
if (d[x][y] < d[x][id]) {
d[x][id] = d[x][y];
dq.emplace_front(x, id);
}
}
}
}
int ans = *min_element(d[b[1]].begin(), d[b[1]].end());
if (ans == inf) {
ans = -1;
}
cout << ans << "\n";
return 0;
}
