from heapq import *
MAX_INT = int(2E9)
class Edge(object):
def __init__(self, to, weight):
self.to = to
self.weight = weight
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 dijkstra(V, start, adj_list):
Q = []
dist = [MAX_INT for i in range(V)]
dist[start] = 0
heappush(Q, Node(start, 0))
while Q:
u = Q[0].u
dist_u = Q[0].dist
heappop(Q)
if dist[u] < dist_u :
continue
for i in range(len(adj_list[u])):
v = adj_list[u][i].to
dist_v = dist_u + adj_list[u][i].weight
if dist_v < dist[v]:
dist[v] = dist_v
heappush(Q, Node(v, dist_v))
return dist
N, M = map(int, raw_input().split())
doge = [None]*M
for i in range(M):
doge[i] = map(int, raw_input().split())
adj_list = [ [] for i in range(M) ]
for i in range(M):
for j in range(M):
if i != j and ((doge[i][0] - doge[j][0])%doge[i][1] == 0 ):
adj_list[i].append(Edge(j, abs(doge[i][0] - doge[j][0])/doge[i][1]))
ans = dijkstra(M, 0, adj_list)
if ans[1] == MAX_INT:
print -1
else:
print ans[1]
