#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ll n,m,a,b,i,j,k,q;
cin>>n>>m;
vector<pair<ll,ll>> bird(m);
vector<vector<ll>> jump(n);
for(i=0 ; i<m ; i++){
cin>>bird[i].first>>bird[i].second;
ll pos=bird[i].first;
ll power=bird[i].second;
jump[pos].push_back(power);
}
priority_queue<pair<ll,ll>> pq;
pq.push({0,bird[0].first});
vector<ll> dj(n,1e9);
dj[bird[0].first]=0;
while(pq.size()){
ll dist=-pq.top().first;
ll u=pq.top().second;
pq.pop();
for(auto v:jump[u]){
ll pos=u;
ll cnt=0;
while(pos+v<n){
pos+=v;
cnt++;
if(dist+cnt<dj[pos]){
dj[pos]=dist+cnt;
pq.push({-dj[pos],pos});
}
}
while(pos-v>=0){
pos-=v;
cnt++;
if(dist+cnt<dj[pos]){
dj[pos]=dist+cnt;
pq.push({-dj[pos],pos});
}
}
}
}
if(dj[bird[1].first]<1e9) cout<<dj[bird[1].first]<<"\n";
else cout<<-1<<"\n";
return 0;
}
