#include <stdio.h>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int P,N,B[30003],V[30003]; vector<int> G[30003];
int c,u[2][60003],v[2][60003],d[30003];
set<int> chk[30003];
void add(int t, int x)
{
u[t][c] = B[x]; v[t][c] = +V[x]; c++;
u[t][c] = B[x]; v[t][c] = -V[x]; c++;
}
int main()
{
scanf ("%d %d",&P,&N);
for (int i=0;i<P;i++) d[i] = -1;
for (int i=0;i<N;i++){
scanf ("%d %d",&B[i],&V[i]);
G[B[i]].push_back(i);
}
d[B[0]] = 0;
for (int x : G[B[0]]) add(0,x);
for (int p=1;;p++){
int lc = c; c = 0; bool ed = 1;
int pr = (p + 1) % 2, nx = p % 2;
for (int i=0;i<lc;i++){
u[pr][i] += v[pr][i];
if (0 <= u[pr][i] && u[pr][i] < P){
ed = 0;
if (!chk[u[pr][i]].count(abs(v[pr][i]))){
u[nx][c] = u[pr][i]; v[nx][c] = v[pr][i]; c++;
}
if (d[u[pr][i]] == -1){
d[u[pr][i]] = p; ed = 0;
chk[u[pr][i]].insert(abs(v[pr][i]));
for (int x : G[u[pr][i]]){
if (abs(v[pr][i]) != V[x]){
add(nx,x);
chk[u[pr][i]].insert(V[x]);
}
}
}
}
}
if (ed) break;
}
printf ("%d\n",d[B[1]]);
return 0;
}
