from collections import deque, defaultdict
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: BFS Initialization
queue = deque([(doges[0][0], 0)]) # (current position, jumps used)
visited = set([(doges[0][0], 0)]) # (skyscraper, doge index)
while queue:
pos, jumps = queue.popleft()
# If we've reached Doge 1, return jumps used
if pos == doges[1][0]:
return jumps
# Step 3: Check same-skyscraper doges (news passing)
for idx, power in skyscraper_doges[pos]:
if (pos, idx) not in visited:
visited.add((pos, idx))
queue.append((pos, jumps))
# Step 4: Explore possible jumps
if pos + power < N and (pos + power, idx) not in visited:
visited.add((pos + power, idx))
queue.append((pos + power, jumps + 1))
if pos - power >= 0 and (pos - power, idx) not in visited:
visited.add((pos - power, idx))
queue.append((pos - power, jumps + 1))
return -1 # No way to reach Doge 1
# Read input
N, M = map(int, input().split())
doges = [tuple(map(int, input().split())) for _ in range(M)]
# Output the result
print(min_jumps_to_doge1(N, M, doges))
