import heapq
from collections import defaultdict
import sys
# Constants
BUC = 175 # Jump threshold
INF = float('inf')
def min_jumps_to_doge1(N, M, doges):
# Step 1: Construct adjacency list (doges per skyscraper)
skyscraper_doges = defaultdict(list)
for i, (B, P) in enumerate(doges):
skyscraper_doges[B].append((i, P)) # Doge index and power
# Step 2: Dijkstra Initialization
dist = {} # Dictionary to store the minimum jumps needed
pq = [] # Min heap for Dijkstra's algorithm
# Push starting position (Doge 0) into priority queue
heapq.heappush(pq, (0, doges[0][0], 0)) # (jumps, position, power)
dist[(doges[0][0], 0)] = 0 # Distance to Doge 0's initial position is 0
while pq:
jumps, pos, power = heapq.heappop(pq)
# If we reach Doge 1, return the minimum jumps
if pos == doges[1][0]:
return jumps
# Step 3: Passing news to other doges at the same skyscraper
for _, new_power in skyscraper_doges[pos]:
if (pos, new_power) not in dist or dist[(pos, new_power)] > jumps:
dist[(pos, new_power)] = jumps
heapq.heappush(pq, (jumps, pos, new_power))
# Step 4: Moving using jumps
if power > 0: # If doge has jumping power
for new_pos in (pos + power, pos - power):
if 0 <= new_pos < N: # Ensure within bounds
if (new_pos, 0) not in dist or dist[(new_pos, 0)] > jumps + 1:
dist[(new_pos, 0)] = jumps + 1
heapq.heappush(pq, (jumps + 1, new_pos, 0))
return -1 # If we never reach Doge 1
# Read input
N, M = map(int, sys.stdin.readline().split())
doges = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
# Output the result
print(min_jumps_to_doge1(N, M, doges))
