from heapq import *
from bisect import bisect_right
maxint = int(2E9)
class Node(object):
def __init__(self, u, dist):
self.u = u
self.dist = dist
def __cmp__(self, other):
return cmp(self.dist, other.dist)
def binary_search(L, val):
if not L : return False
s = bisect_right(L, val)
return L[s-1] == val
def dijkstra(start):
global N, M, V, B, P
dist = [maxint for i in range(N)]
start = B[0]
dist[start] = 0
Q = []
heappush(Q, Node(start, 0))
while Q :
node = heappop(Q)
u, dist_u = node.u, node.dist
if dist_u > dist[u] : continue
for power in V[u]:
to = u+power
cost = dist_u + 1
while to < N :
if dist[to] > cost :
dist[to] = cost
heappush(Q, Node(to, cost))
if binary_search(V[to], power):
break
to += power
cost += 1
to = u-power
cost = dist_u + 1
while to >= 0 :
if dist[to] > cost :
dist[to] = cost
heappush(Q, Node(to, cost))
if binary_search(V[to], power):
break
to -= power
cost += 1
return dist
def main():
global N, M, V, B, P
N, M = map(int, raw_input().split())
V = [ [] for i in range(N) ]
B = [None for i in range(M)]
P = [None for i in range(M)]
for i in range(M):
B[i], P[i] = map(int, raw_input().split())
V[B[i]].append(P[i])
for i in range(N):
V[i] = list(set(V[i]))
V[i].sort()
start = B[0]
dist = dijkstra(start)
ans = dist[B[1]]
if ans == maxint: print -1
else: print ans
return
main()
