#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n,m;
if(!(cin>>n>>m))return 0;
vector<int>b(m),p(m);
vector<vector<int>> at(n);
for(int i=0;i<m;i++){
cin>>b[i]>>p[i];
at[b[i]].push_back(i);
}
const ll INF = LLONG_MAX/4;
vector<ll> dist(m,INF);
vector<char> vis(m,0);
dist[0]=0;
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
pq.push({0,0});
while(!pq.empty()){
auto [d,i] = pq.top(); pq.pop();
if(vis[i]) continue;
vis[i]=1;
if(i==1) break;
int bi=b[i], pi=p[i];
// jump right
for(ll k=1, x=bi+pi; x<n; x+=pi, ++k){
for(int j: at[x]) if(!vis[j] && dist[j] > d + k){ dist[j] = d + k; pq.push({dist[j], j}); }
}
// jump left
for(ll k=1, x=bi-pi; x>=0; x-=pi, ++k){
for(int j: at[x]) if(!vis[j] && dist[j] > d + k){ dist[j] = d + k; pq.push({dist[j], j}); }
}
}
ll ans = dist[1];
if(ans==INF) cout<<-1;
else cout<<ans;
return 0;
}
