#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N = 30003;
struct node{
int at,cost;
node(int a, int b){
at = a,cost = b;
}
};
bool operator<(node A,node B){
return A.cost > B.cost;
}
vector<pii>edges,graph[N];
int dist[N];
map<pii,bool>vis;
int dijkstra(int s,int dst,int n)
{
priority_queue<node>pq;
for(int i = 0; i < n;i++)dist[i] = 999999999;
dist[s] = 0;
pq.push(node(s,0));
while(!pq.empty()){
node u = pq.top();
//printf("%d\n",u.at);
pq.pop();
if(u.cost != dist[u.at])continue;
for(pii e: graph[u.at]){
//printf("%d: %d -- %d,%d\n",u.at,e.first,dist[e.first],u.cost+e.second);
if(dist[e.first] > u.cost+e.second){
dist[e.first] = u.cost+e.second;
pq.push(node(e.first,dist[e.first]));
}
}
//exit(0);
}
return dist[dst];
}
int main(int argc, char const *argv[])
{
int n,m,b,a;
scanf("%d%d",&n,&m);
int src = -1,destination = -1;
for(int i = 0; i < m;i++){
scanf("%d%d",&a,&b);
if(vis[{a,b}])continue;
vis[{a,b}] = vis[{b,a}] = true;
if(i == 0)src = a;
if(i == 1)destination = a;
int x = 1;
while(a+b*x < n){
graph[a].push_back({a+b*x,x});
x++;
}
x = 1;
while(a-b*x >= 0){
graph[a].push_back({a-b*x,x});
x++;
}
}
//printf("%d %d\n",src,destination);exit(0);
int k = dijkstra(src,destination,n);
if(k == 999999999)printf("-1\n");
else printf("%d\n",k);
return 0;
}
