#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
typedef pair<int,pair<int,int>> pp;
int N,M;
int B[30005],P[30005];
vector<int> V[30005];
deque<pp> Q;
int main(){
cin>>N>>M;
for(int i=0;i<M;i++){
cin>>B[i]>>P[i];
if(i)
V[B[i]].push_back(i);
}
//indice distanza posizione
Q.push_back({0,{0,B[0]}});
while(!Q.empty()){
pp p=Q.front();
Q.pop_front();
//cout<<Q.size()<<" "<<p.first<<" "<<p.second.first<<" "<<p.second.second<<endl;
if(p.first==1){
cout<<p.second.first;
return 0;
}
for(int x:V[p.second.second])
Q.push_front({x,{p.second.first,B[x]}});
V[p.second.second].clear();
if(p.second.second==B[p.first]){
for(int k=1;;k++){
if(p.second.second-k*P[p.first]<0)
break;
if(!V[p.second.second-k*P[p.first]].empty()){
Q.push_back({p.first,{p.second.first+k,p.second.second-k*P[p.first]}});
break;
}
}
for(int k=1;;k++){
if(p.second.second+k*P[p.first]>=N)
break;
if(!V[p.second.second+k*P[p.first]].empty()){
Q.push_back({p.first,{p.second.first+k,p.second.second+k*P[p.first]}});
break;
}
}
}
if(p.second.second<B[p.first]){
for(int k=1;;k++){
if(p.second.second-k*P[p.first]<0)
break;
if(!V[p.second.second-k*P[p.first]].empty()){
Q.push_back({p.first,{p.second.first+k,p.second.second-k*P[p.first]}});
break;
}
}
}
if(p.second.second>B[p.first]){
for(int k=1;;k++){
if(p.second.second+k*P[p.first]>=N)
break;
if(!V[p.second.second+k*P[p.first]].empty()){
Q.push_back({p.first,{p.second.first+k,p.second.second+k*P[p.first]}});
break;
}
}
}
}
cout<<-1;
}
