#include<stdio.h>
#include<algorithm>
#include<vector>
#include<map>
#define N_ 7600000
using namespace std;
int n, m, Num[N_], D[N_], Q1[N_], Q2[N_];
vector<int>E[30100];
map<int, int>Map;
bool be[N_], ed[N_];
struct A{
int a, b;
}w[30100];
int cnt;
void Make(int a, int b, int x){
int i;
be[cnt + 1] = true;
for (i = b; i < n; i += a){
++cnt;
Num[cnt] = i;
if (x == i) E[x].push_back(cnt);
}
ed[cnt] = true;
}
void BFS(int a){
int i, h = 0, t = 0, tt = 0, x;
for (i = 0; i <= cnt; i++)D[i] = 999999999;
D[a] = 0;
Q1[++t] = a;
while (t){
while (h < t){
x = Q1[++h];
if (x<n){
for (i = 0; i<E[x].size(); i++){
if (D[E[x][i]] > D[x]){
D[E[x][i]] = D[x];
Q1[++t] = E[x][i];
}
}
}
else{
if (D[Num[x]] > D[x]){
D[Num[x]] = D[x];
Q1[++t] = Num[x];
}
}
}
tt = 0;
for (i = 1; i <= t; i++){
if (Q1[i]<n)continue;
x = Q1[i];
if (!be[x] && D[x - 1] >D[x] + 1){
D[x - 1] = D[x] + 1;
Q2[++tt] = x - 1;
}
if (!ed[x] && D[x + 1] > D[x] + 1){
D[x + 1] = D[x] + 1;
Q2[++tt] = x + 1;
}
}
for (i = 1; i <= tt; i++)Q1[i] = Q2[i];
t = tt;
h = 0;
}
}
int main(){
int i, p1, p2, t;
scanf("%d%d", &n, &m);
cnt = n;
for (i = 1; i <= m; i++){
scanf("%d%d", &w[i].a, &w[i].b);
t = w[i].b * 30100 + (w[i].a%w[i].b);
if (!Map[t]){
Map[t] = cnt + 1;
Make(w[i].b, w[i].a%w[i].b, w[i].a);
}
else{
E[w[i].a].push_back(Map[t] + w[i].a / w[i].b);
}
}
p1 = w[1].a, p2 = w[2].a;
BFS(p1);
printf("%d\n", D[p2] == 999999999 ? -1 : D[p2]);
}
