#include <bits/stdc++.h>
using namespace std;
int const MAX=30005;
int n,m;
int pos[MAX],pas[MAX];
bitset<MAX>vis[MAX];
bool Vis[MAX];
vector<int>puteri[MAX];
void read(){
cin>>n>>m;
int i;
for(i=0;i<m;++i){
cin>>pos[i]>>pas[i];
puteri[pos[i]].push_back(pas[i]);
}
}
struct traseu{
int poz,power,len;
};
int bfs(){
int pos0=pos[0];
int pos1=pos[1];
queue<traseu>q;
for(auto put : puteri[pos0]){
q.push({pos0,put,0});
vis[pos0][put]=1;
}
Vis[pos0]=1;
while(!q.empty()){
auto [poz,put,len]=q.front();
q.pop();
if(poz==pos1)
return len;
if(poz-put>=0){
if(!vis[poz-put][put]){
vis[poz-put][put]=1;
q.push({poz-put,put,len+1});
if(!Vis[poz-put])
for(auto puter : puteri[poz-put])
if(!vis[poz-put][puter]){
vis[poz-put][puter]=1;
q.push({poz-put,puter,len+1});
}
}
}
if(poz+put<n){
if(!vis[poz+put][put]){
vis[poz+put][put]=1;
q.push({poz+put,put,len+1});
if(!Vis[poz+put])
for(auto puter : puteri[poz+put])
if(!vis[poz+put][puter]){
vis[poz+put][puter]=1;
q.push({poz+put,puter,len+1});
}
}
}
}
return -1;
}
int main()
{
read();
cout<<bfs();
return 0;
}
