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