#include<bits/stdc++.h>
#define MAXN 30007
using namespace std;
struct doge{
int pos,jump;
inline friend bool operator < (doge fr,doge sc){
if(fr.jump!=sc.jump)return fr.jump<sc.jump;
if(fr.pos%fr.jump!=sc.pos%sc.jump)return fr.pos%fr.jump<sc.pos%sc.jump;
return fr.pos<sc.pos;
}
}d[MAXN];
int n,m,dist[MAXN];
vector<doge> w;
vector< pair<int,int> > v[MAXN];
priority_queue < pair<int,int> , vector< pair<int,int> > , greater< pair<int,int> > > q;
bool vis[MAXN];
void add_edge(int x,int y,int z){
v[x].push_back({y,z});
}
void dijkstra(int x){
for(int i=0;i<n;i++)dist[i]=n*n;
dist[x]=0;
q.push({0,x});
while(!q.empty()){
int minv=q.top().second;
q.pop();
if(vis[minv])continue;
vis[minv]=true;
for(auto nxt:v[minv]){
if(vis[nxt.first] or dist[nxt.first]<=dist[minv]+nxt.second)continue;
dist[nxt.first]=dist[minv]+nxt.second;
q.push({dist[nxt.first],nxt.first});
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>d[i].pos>>d[i].jump;
}
int st=d[1].pos;
int et=d[2].pos;
sort(d+1,d+m+1);
for(int i=1;i<=m;i++){
if(i<m and d[i].jump==d[i+1].jump and d[i].pos%d[i].jump==d[i+1].pos%d[i+1].jump){
w.push_back(d[i]);
continue;
}
w.push_back(d[i]);
for(int i=0;i<w.size();i++){
for(int t=1;(i==0 or w[i].pos-t*w[i].jump>=w[i-1].pos) and w[i].pos-t*w[i].jump>=0;t++){
add_edge(w[i].pos,w[i].pos-t*w[i].jump,t);
}
for(int t=1;(i==w.size()-1 or w[i].pos+t*w[i].jump<=w[i+1].pos) and w[i].pos+t*w[i].jump<n;t++){
add_edge(w[i].pos,w[i].pos+t*w[i].jump,t);
}
}
w.clear();
}
dijkstra(st);
if(!vis[et]){
cout<<"-1\n";
}else{
cout<<dist[et]<<"\n";
}
return 0;
}
