#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10;
vector<pair<int,int>> adj[N];
int pos[N],p[N],d[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
set<pair<int,pair<int,int>>> s;
set<pair<int,int>> ck;
bool vs[N];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m;
cin>>n >>m;
for(int i=0;i<m;i++){
cin>>pos[i] >>p[i];
if(ck.find({pos[i],p[i]})!=ck.end()) continue;
ck.insert({pos[i],p[i]});
for(int j=pos[i];j>=0;j-=p[i]){
if(j==pos[i]) continue;
if(s.find({pos[i],{j,(pos[i]-j)/p[i]}})!=s.end()) break;
adj[pos[i]].push_back({j,(pos[i]-j)/p[i]});
s.insert({pos[i],{j,(pos[i]-j)/p[i]}});
}
for(int j=pos[i];j<n;j+=p[i]){
if(j==pos[i]) continue;
if(s.find({pos[i],{j,(pos[i]-j)/p[i]}})!=s.end()) break;
adj[pos[i]].push_back({j,(j-pos[i])/p[i]});
s.insert({pos[i],{j,(j-pos[i])/p[i]}});
}
}
int st=pos[0],ed=pos[1];
for(int i=0;i<n;i++) d[i]=INT_MAX;
d[st]=0;
q.push({0,st});
while(!q.empty()){
int u=q.top().second;
q.pop();
if(vs[u]) continue;
vs[u]=true;
for(auto [v,w]:adj[u]){
if(d[u]+w<d[v]){
d[v]=d[u]+w;
q.push({d[v],v});
}
}
}
if(d[ed]==INT_MAX) cout<<-1;
else cout<<d[ed];
}
