import io, os
from math import *
from heapq import *
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n, m = map(int, input().split())
edges = [[] for i in range(n)]
sussy = [[] for i in range(n)]
stuff = set()
count = 0
for i in range(m):
a,b = map(int, input().split())
if count == 1:
baka = a
if count == 0:
imposter = a
#sussy[a].append(b)
stuff.add((a,b))
count += 1
for i in stuff:
sus = i[0]
count = 0
while (sus+i[1])<n:
sus+=i[1]
count += 1
edges[i[0]].append((sus, count))
sus = i[0]
count = 0
while (sus-i[1])>=0:
sus -= i[1]
count += 1
edges[i[0]].append((sus, count))
def djk(src):
dist = [inf for i in range(n)]
dist[src] = 0
q = []
heapify(q)
heappush(q, (dist[src], src))
while len(q):
node = heappop(q)
if dist[node[1]] != node[0]:
continue
for i in edges[node[1]]:
if dist[i[0]] > node[0] + i[1]:
dist[i[0]] = node[0] + i[1]
heappush(q, (node[0]+i[1], i[0]))
return dist
susz = djk(imposter)[baka]
print(-1 if susz == inf else susz)
