#include <bits/stdc++.h>
using namespace std;
const int MAXN = 30005;
int N, M;
vector<pair<int, int>> doges; // (position, power)
vector<vector<int>> building(MAXN); // doges in each building
vector<vector<int>> visited; // visited[doge_index][position]
queue<tuple<int, int, int>> q; // (doge_index, position, steps)
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M;
doges.resize(M);
visited.assign(M, vector<int>(N, -1));
for (int i = 0; i < M; ++i) {
int b, p;
cin >> b >> p;
doges[i] = {b, p};
building[b].push_back(i);
}
// Start from doge 0
q.emplace(0, doges[0].first, 0);
visited[0][doges[0].first] = 0;
while (!q.empty()) {
auto [idx, pos, steps] = q.front();
q.pop();
// If reached doge 1
if (idx == 1) {
cout << steps << '\n';
return 0;
}
int power = doges[idx].second;
// Jump to the left
for (int next = pos - power; next >= 0; next -= power) {
if (visited[idx][next] != -1) break;
visited[idx][next] = steps + 1;
q.emplace(idx, next, steps + 1);
}
// Jump to the right
for (int next = pos + power; next < N; next += power) {
if (visited[idx][next] != -1) break;
visited[idx][next] = steps + 1;
q.emplace(idx, next, steps + 1);
}
// Pass message to other doges in the same building
for (int other_idx : building[pos]) {
if (visited[other_idx][pos] == -1) {
visited[other_idx][pos] = steps + 1;
q.emplace(other_idx, pos, steps + 1);
}
}
// Clear the building to prevent redundant processing
building[pos].clear();
}
// If doge 1 is unreachable
cout << -1 << '\n';
return 0;
}
