#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<pair<int,int>,int> pp;
int N,M;
int B[30005],P[30005];
vector<int> V[30005];
priority_queue<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
// |
// |
// |
// V
//dist pos ind
Q.push({{0,B[0]},0});
while(!Q.empty()){
pp p=Q.top();
Q.pop();
//cout<<Q.size()<<" "<<p.second<<" "<<p.first.first<<" "<<p.first.second<<endl;
if(p.second==1){
cout<<p.first.first;
return 0;
}
for(int x:V[p.first.second])
Q.push({{p.first.first,B[x]},x});
V[p.first.second].clear();
if(p.first.second==B[p.second]){
for(int k=1;;k++){
if(p.first.second-k*P[p.second]<0)
break;
if(!V[p.first.second-k*P[p.second]].empty()){
Q.push({{p.first.first+k,p.first.second-k*P[p.second]},p.second});
break;
}
}
for(int k=1;;k++){
if(p.first.second+k*P[p.second]>=N)
break;
if(!V[p.first.second+k*P[p.second]].empty()){
Q.push({{p.first.first+k,p.first.second+k*P[p.second]},p.second});
break;
}
}
}
if(p.first.second<B[p.second]){
for(int k=1;;k++){
if(p.first.second-k*P[p.second]<0)
break;
if(!V[p.first.second-k*P[p.second]].empty()){
Q.push({{p.first.first+k,p.first.second-k*P[p.second]},p.second});
break;
}
}
}
if(p.first.second>B[p.second]){
for(int k=1;;k++){
if(p.first.second+k*P[p.second]>=N)
break;
if(!V[p.first.second+k*P[p.second]].empty()){
Q.push({{p.first.first+k,p.first.second+k*P[p.second]},p.second});
break;
}
}
}
}
cout<<-1;
}
