#include <bits/stdc++.h>
using namespace std;
int cor[30005][3];
vector<pair<int,int> > adj[7000000];
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin >> n >> m;
int c=30001;
for(int i=0; i<n; i++){
for(int j=1; j<3; j++){
cor[i][j]=c;
c++;
}
}
for(int i=0; i<n; i++){
for(int j=1; j<3; j++){
if(i+j<n){
adj[cor[i][j]].push_back({cor[i+j][j],1});
adj[cor[i+j][j]].push_back({cor[i][j],1});
}
adj[cor[i][j]].push_back({i,0});
}
}
int s=0,e=0;
for(int i=0; i<m; i++){
int a,b;
cin >> a >> b;
if(i==0) s=a;
if(i==1) e=a;
if(b<3){
adj[a].push_back({cor[a][b],0});
}
else{
for(int j=1; j<n; j++){
if(a+j*b>=n) break;
adj[a].push_back({a+j*b,j});
}
for(int j=1; j<n; j++){
if(a-j*b<0) break;
adj[a].push_back({a-j*b,j});
}
}
}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
pq.push({0,s});
int dist[5000000];
for(int i=0; i<5000000; i++) dist[i]=1e7;
dist[s]=0;
while(!pq.empty()){
int a=pq.top().first,b=pq.top().second;
pq.pop();
if(a>dist[b]) continue;
//cout << b << ' ' << a << '\n';
if(b==e){
cout << a;
return 0;
}
for(auto i:adj[b]){
if(dist[i.first]<=a+i.second) continue;
dist[i.first]=a+i.second;
pq.push({a+i.second,i.first});
}
}
cout << -1;
}
