#include <bits/stdc++.h> using namespace std; #define REP(i,n) for (int i = 0; i < n; i++) typedef long long ll; const ll INF = (ll)1e13; const int MAXN = 105, MAXP = 105, MAXM = 2005; int N, M; int B[MAXM], P[MAXM]; priority_queue<tuple<ll, int, int>> pq; ll dist[MAXN][MAXP]; bool powers[MAXN][MAXP]; ll solve() { REP(i, M) powers[B[i]][P[i]] = true; REP(i, N) REP(j, MAXP) dist[i][j] = INF; dist[B[0]][P[0]] = 0; pq.emplace(0, B[0], P[0]); while (!pq.empty()) { ll d; int building, power; tie(d, building, power) = pq.top(); pq.pop(); if (-d > dist[building][power]) continue; if (building == B[1]) return -d; // move for (int sign = -1; sign <= 1; sign += 2) { int new_building = building + sign * power; if (new_building < 0 || new_building >= N) continue; if (dist[new_building][power] > dist[building][power] + 1) { dist[new_building][power] = dist[building][power] + 1; pq.emplace(-dist[new_building][power], new_building, power); } } // pass news REP(new_power, MAXP) if (powers[building][new_power] && dist[building][new_power] > dist[building][power]) { dist[building][new_power] = dist[building][power]; pq.emplace(-dist[building][new_power], building, new_power); } } return -1; } int main() { cin >> N >> M; REP(i, M) cin >> B[i] >> P[i]; cout << solve() << endl; }