#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nl '\n'
const int N = 3e4, sq = 175;
vector<pair<int,int>> g[N];
int prnt[N][sq];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
vector<int> vis(N, 0);
vector<int> dist(N, 1e18);
inline void solve(){
int n, m, st, dt;
cin>>n>>m;
for(int i=0; i<m; i++){
int b, p;
cin>>b>>p;
if(i == 0) st = b;
if(i == 1) dt = b;
if(p < sq){
prnt[b][p] = 1;
continue;
}
for(int j=b-p, c = 1; j>=0; j -= p, c++) g[b].push_back({j, c});
for(int j=b+p, c = 1; j<n; j += p, c++) g[b].push_back({j, c});
}
for(int i=0; i<n; i++){
for(int p=0; p<sq; p++){
if(!prnt[i][p]) continue;
for(int j=i-p, c = 1; j>=0; j -= p, c++){
g[i].push_back({j, c});
if(prnt[j][p]) break;
}
for(int j=i+p, c = 1; j<n; j += p, c++){
g[i].push_back({j, c});
if(prnt[j][p]) break;
}
}
}
pq.push({0, st});
dist[st] = 0;
while(!pq.empty()){
auto [d, v] = pq.top();
pq.pop();
if(vis[v]) continue;
vis[v] = 1;
for(auto [ch, w] : g[v]){
if(d + w < dist[ch]){
dist[ch] = d + w;
pq.push({dist[ch], ch});
}
}
}
cout<<(dist[dt] == 1e18 ? -1 : dist[dt])<<nl;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);cout.tie(NULL);
int t = 1;
//cin>>t;
while(t--) solve();
return 0;
}
