#include <bits/stdc++.h>
using namespace std;
int edge[21000005], nxt[21000005], lnk[10500005], dist[10500005], deq[2000005], a[30005][175], n, m, mm, s, t, sz, cnt, l=1000000, r=1000001;
void add(int u, int x)
{
edge[++cnt]=x;
nxt[cnt]=lnk[u];
lnk[u]=cnt;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
mm=sqrt(m);
sz=n;
for (int i=0; i!=m; i++)
{
int b, p;
cin >> b >> p;
if (!i)
s=b;
else if (i==1)
t=b;
if (p<=mm)
{
if (!a[b][p])
{
int rem=b%p;
a[rem][p]=sz++;
add(a[rem][p], rem<<1);
for (int j=rem+p; j<n; j+=p)
{
a[j][p]=sz++;
add(a[j][p], j<<1);
add(a[j][p], a[j-p][p]<<1|1);
add(a[j-p][p], a[j][p]<<1|1);
}
}
add(b, a[b][p]<<1);
}
else
{
int prev=b;
for (int j=b-p; j>=0; j-=p)
{
add(prev, sz<<1|1);
add(sz, j<<1);
prev=sz++;
}
prev=b;
for (int j=b+p; j<n; j+=p)
{
add(prev, sz<<1|1);
add(sz, j<<1);
prev=sz++;
}
}
}
for (int i=0; i!=sz; i++)
dist[i]=1e9;
dist[s]=0;
deq[1000000]=s;
while (l!=r)
{
int u=deq[l++], cur;
cur=lnk[u];
while (cur)
{
int v=edge[cur]>>1, w=edge[cur]&1;
if (dist[v]==1e9)
{
dist[v]=dist[u]+w;
if (w)
deq[r++]=v;
else
deq[--l]=v;
}
cur=nxt[cur];
}
}
if (dist[t]==1e9)
cout << -1;
else
cout << dist[t];
return 0;
}
