#include<bits/stdc++.h>
#define ll int
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<pair<ll,ll>>> e(n+1);
for(i=0 ; i<m ; i++){
cin>>bird[i].first>>bird[i].second;
ll pos=bird[i].first;
ll pos0=bird[i].first;
while(pos+bird[i].second<n){
pos+=bird[i].second;
e[pos0].push_back({pos,(pos-pos0)/bird[i].second});
}
pos=bird[i].first;
pos0=bird[i].first;
while(pos-bird[i].second>=0){
pos-=bird[i].second;
e[pos0].push_back({pos,(pos0-pos)/bird[i].second});
}
}
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:e[u]){
if(dist+v.second<dj[v.first]){
dj[v.first]=dist+v.second;
pq.push({-dj[v.first],v.first});
}
}
}
if(dj[bird[1].first]<1e9) cout<<dj[bird[1].first]<<"\n";
else cout<<-1<<"\n";
return 0;
}
