#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 30005;
const int S = 170; // threshold approx sqrt(30000)
const int INF = 1e9;
// dist[u][p] = min jumps to be at skyscraper u with active jumping power p
// p = 0 means being at skyscraper u without an active jump (stopped)
int dist[MAXN][S + 5];
vector<int> doges[MAXN];
struct State {
int d, u, p;
bool operator>(const State& other) const {
return d > other.d; // For min-heap priority queue
}
};
int main() {
// Optimize standard I/O operations for performance
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
if (!(cin >> N >> M)) return 0;
int start_pos = -1, target_pos = -1;
for (int i = 0; i < M; i++) {
int b, p;
cin >> b >> p;
if (i == 0) start_pos = b;
if (i == 1) target_pos = b;
doges[b].push_back(p);
}
// Remove duplicate doge powers at the same skyscraper to avoid redundant processing
for (int i = 0; i < N; i++) {
if (!doges[i].empty()) {
sort(doges[i].begin(), doges[i].end());
doges[i].erase(unique(doges[i].begin(), doges[i].end()), doges[i].end());
}
}
// Initialize distances to Infinity
for (int i = 0; i < N; i++) {
for (int j = 0; j <= S; j++) {
dist[i][j] = INF;
}
}
priority_queue<State, vector<State>, greater<State>> pq;
// Start with Doge 0 at its initial building, in a stopped state (p = 0)
dist[start_pos][0] = 0;
pq.push({0, start_pos, 0});
while (!pq.empty()) {
State curr = pq.top();
pq.pop();
int d = curr.d;
int u = curr.u;
int p = curr.p;
// Skip if we already found a shorter path to this state
if (d > dist[u][p]) continue;
// Since we are looking for the shortest path to Doge 1's building,
// reaching it guarantees the shortest possible message delivery.
if (u == target_pos) {
cout << d << "\n";
return 0;
}
if (p == 0) {
// We are at a skyscraper and can wake up doges located here
for (int pw : doges[u]) {
if (pw <= S) {
// Small jump power: Enter active jumping state
if (d < dist[u][pw]) {
dist[u][pw] = d;
pq.push({d, u, pw});
}
} else {
// Large jump power: Jump directly and add resulting locations
// Jump right
for (int jump = 1; u + jump * pw < N; jump++) {
int v = u + jump * pw;
int cost = d + jump;
if (cost < dist[v][0]) {
dist[v][0] = cost;
pq.push({cost, v, 0});
}
}
// Jump left
for (int jump = 1; u - jump * pw >= 0; jump++) {
int v = u - jump * pw;
int cost = d + jump;
if (cost < dist[v][0]) {
dist[v][0] = cost;
pq.push({cost, v, 0});
}
}
}
}
} else {
// We are in an active jumping state with power `p`
// 1. Stop at the current skyscraper
if (d < dist[u][0]) {
dist[u][0] = d;
pq.push({d, u, 0});
}
// 2. Continue jumping right
if (u + p < N) {
if (d + 1 < dist[u + p][p]) {
dist[u + p][p] = d + 1;
pq.push({d + 1, u + p, p});
}
}
// 3. Continue jumping left
if (u - p >= 0) {
if (d + 1 < dist[u - p][p]) {
dist[u - p][p] = d + 1;
pq.push({d + 1, u - p, p});
}
}
}
}
// If queue is empty and target_pos was never reached
cout << -1 << "\n";
return 0;
}
