#include <bits/stdc++.h> #pragma GCC optimize("O3") #define FOR(i, x, y) for (ll i = x; i < y; i++) typedef long long ll; using namespace std; struct Doge { ll jumps, pos, size, direction; }; vector<pair<ll, ll>> sky[300001]; bool visited[300001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); fill(visited, visited + 300001, false); ll n, m; cin >> n >> m; ll size = 0, pos = 0; FOR(i, 0, m) { ll a, b; cin >> a >> b; sky[a].push_back({i, b}); if (i == 0) size = b, pos = a; } queue<Doge> q; q.push({0, pos, size, 1}); while (!q.empty()) { Doge curr = q.front(); q.pop(); // cout << curr.jumps << ' ' << curr.pos << ' ' << curr.size << ' ' // << curr.direction << '\n'; if (curr.pos > -1 && curr.pos < n && !visited[curr.pos]) { visited[curr.pos] = true; for (auto& i : sky[curr.pos]) { if (i.first == 1) return cout << curr.jumps << '\n', 0; if (i.second != curr.size) { q.push({curr.jumps + 1, curr.pos + i.second, i.second, 1}); q.push({curr.jumps + 1, curr.pos - i.second, i.second, 0}); } } } if (curr.direction && curr.pos + curr.size < n) q.push({curr.jumps + 1, curr.pos + curr.size, curr.size, 1}); else if ((!curr.direction) && curr.pos - curr.size > -1) q.push({curr.jumps + 1, curr.pos - curr.size, curr.size, 0}); } cout << "-1\n"; return 0; }