#include "bits/stdc++.h" using namespace std; const int MAXN = 2007; const int MAXM = 30007; const int INF_INT = 2147483647; int n,m; vector<int> arr[MAXN]; int power[MAXM]; vector<vector<int>> dist(MAXM,vector<int>(MAXN)); // int dist[MAXM][MAXN]; deque<pair<int,int>> dq; bool seenposition[MAXN]; int main() { #ifdef LOCAL freopen("submission/input.in", "r", stdin); freopen("submission/output.out", "w", stdout); #else ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #endif cin >> n >> m; int start,end; // memset(dist,10,sizeof(dist)); for (int i = 0; i<m; i++) for (int j = 0; j<n; j++) dist[i][j] = INF_INT; for (int i = 0; i<m; i++) { int x; cin >> x >> power[i]; if (i == 0) start = x; if (i == 1) end = x; arr[x].push_back(i); } dq.push_back({0,start}); dist[0][start] = 0; int jumps = -1; while (!dq.empty()) { int x = dq.front().first, y = dq.front().second; dq.pop_front(); if (0<=y-power[x] && dist[x][y]+1<dist[x][y-power[x]]) { dist[x][y-power[x]] = dist[x][y]+1; dq.push_back({x,y-power[x]}); } if (y+power[x]<n && dist[x][y]+1<dist[x][y+power[x]]) { dist[x][y+power[x]] = dist[x][y]+1; dq.push_back({x,y+power[x]}); } if (seenposition[y]) continue; seenposition[y] = true; if (end == y) { jumps = dist[x][y]; break; } for (int i : arr[y]) { if (i == x) continue; dist[i][y] = dist[x][y]; dq.push_front({i,y}); } } cout << jumps << '\n'; return 0; }