#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N=30005;
int n,m,b[N],p[N],d[N];
vector<pii>adj[N];
vector<int>have[N];
bool Have(int pos, int val)
{
return binary_search(have[pos].begin(), have[pos].end(), val);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>b[i]>>p[i];
b[i]++;
have[b[i]].push_back(p[i]);
}
for(int i=1;i<=n;i++)
{
sort(have[i].begin(),have[i].end());
have[i].erase(unique(have[i].begin(),have[i].end()),have[i].end());
}
for(int i=1;i<=m;i++)
{
int cur=b[i];
int cnt=0;
while(cur+p[i]<=n)
{
cnt++;
cur+=p[i];
adj[b[i]].push_back(mp(cur,cnt));
if(Have(cur,p[i])) break;
}
cur=b[i];
cnt=0;
while(cur-p[i]>=1)
{
cnt++;
cur-=p[i];
adj[b[i]].push_back(mp(cur,cnt));
if(Have(cur,p[i])) break;
}
}
memset(d,-1,sizeof d);
d[b[1]]=0;
priority_queue<pii,vector<pii>,greater<pii>>pq;
pq.push(mp(0,b[1]));
while(!pq.empty())
{
auto u=pq.top();
pq.pop();
if(u.fi!=d[u.se]) continue;
for(auto&v:adj[u.se])
{
if(d[v.fi]==-1||d[v.fi]>u.fi+v.se)
{
d[v.fi]=u.fi+v.se;
pq.push(mp(d[v.fi],v.fi));
}
}
}
cout<<d[b[2]];
}
