#include <iostream>
#include <set>
#include <vector>
using namespace std;
const int NP=3e4+10;
const int NP1=2e3+10;
const int inf=1e9;
int dist[NP1];
int b[NP],p[NP];
vector<pair<int,int>> ma[NP1];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for(int j=0;j<n;j++)
dist[j]=inf;
for(int j=0;j<m;j++)
cin>>b[j]>>p[j];
for(int j=0;j<m;j++)
{
int po=b[j]+p[j];
int le=1;
while(po<n)
{
ma[b[j]].push_back({le,po});
po+=p[j];
le++;
}
po=b[j]-p[j];
le=1;
while(po>=0)
{
ma[b[j]].push_back({le,po});
po-=p[j];
le++;
}
}
set<pair<int,int>> dp;
dp.insert({0,b[0]});
dist[b[0]]=0;
while(dp.size())
{
auto f=*begin(dp);
if(f.second==b[1])
{
cout<<f.first<<endl;
break;
}
dp.erase(begin(dp));
for(auto [ln,vp]:ma[f.second])
{
if(dist[vp]>(f.first+ln))
{
dp.erase({dist[vp],vp});
dist[vp]=f.first+ln;
dp.insert({dist[vp],vp});
}
}
}
if(dist[b[1]]==inf)
cout<<-1<<'\n';
return 0;
}
