#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
const int N = 30000 + 11;
const int MAX = 2e9;
const int T = 1;
int dist[N],a[N],b[N];
bool use[N];
vector<int> v[N];
set<pair<int,int> > s[T+11];
int distt[T+11][N];
set<pair<int,int> > st;
void ups(int d, int l, int p)
{
if (dist[l]>p)
{
st.erase(mp(dist[l],l));
dist[l]=p;
st.insert(mp(dist[l],l));
}
if (distt[d][l]>p)
{
s[d].erase(mp(distt[d][l],l));
distt[d][l]=p;
s[d].insert(mp(distt[d][l],l));
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,m;
cin>>n>>m;
int tt=0;
for (int i=1; i<=m; i++)
{
cin>>a[i]>>b[i];
a[i]++;
v[a[i]].pb(b[i]);
if (i==2) tt=a[i];
}
for (int p=1; p<=T; p++)
{
for (int i=1; i<=n; i++)
{
dist[i]=MAX;
distt[p][i]=MAX;
}
}
dist[a[1]]=0;
st.insert(mp(0,a[1]));
for (int ii=1; ii<=n; ii++)
{
for (int d=1; d<=T; d++)
while (s[d].size()>0)
{
pair<int,int> pp=*s[d].begin();
int to=pp.ss;
if (use[to]==1)
{
s[d].erase(mp(distt[d][to],to));
if (to-d>=1)
ups(d,to-d,distt[d][to]+1);
if (to+d<=n)
ups(d,to+d,distt[d][to]+1);
} else break;
}
pair<int,int> p=*st.begin();
st.erase(p);
int l=p.ss;
for (int t=0; t<v[l].size(); t++)
{
int x=v[l][t];
if (x>T)
{
for (int c=1; l+x*c<=n; c++)
if (dist[l+x*c]>dist[l]+c)
{
int to=l+x*c;
ups(0,to,dist[l]+c);
}
for (int c=1; l-x*c>=1; c++)
if (dist[l-x*c]>dist[l]+c)
{
int to=l-x*c;
ups(0,to,dist[l]+c);
}
} else
{
ups(x,l,dist[l]);
}
}
use[l]=1;
}
if (dist[tt]==MAX) cout<<-1<<endl;
else cout<<dist[tt]<<endl;
}
