#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
signed main(){
ios_base::sync_with_stdio();
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
vector <int> b(m),p(m);
vector <int> s[n];
for(int i=0;i<m;i++){
cin>>b[i]>>p[i];
}
vector <pair <int,int> > g[n];
for(int i=0;i<m;i++){
int x=b[i],cnt=0;
while(x+p[i]<n){
x+=p[i];cnt++;
g[b[i]].pb({x,cnt});
}
x=b[i];cnt=0;
while(x-p[i]>=0){
x-=p[i];cnt++;
g[b[i]].pb({x,cnt});
}
}
/*for(int i=0;i<n;i++){
cout<<i<<"\n";
for(auto x : g[i])cout<<x.ff<<" "<<x.ss<<"\n";
cout<<"\n";
}*/
set <pair <int,int> > st;
vector <int> d(n,1e18);
st.insert({0,b[0]});
d[b[0]]=0;
while(!st.empty()){
int v=st.begin()->second;
st.erase(st.begin());
for(auto to : g[v]){
if(d[to.ff]>d[v]+to.ss){
st.erase({d[to.ff],to.ff});
d[to.ff]=d[v]+to.ss;
st.insert({d[to.ff],to.ff});
}
}
}
if(d[p[1]]==1e18)d[p[1]]=-1;
cout<<d[p[1]]<<"\n";
}
/*
5 3
0 2
1 1
4 1
*/
