#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 3e4+5;
const int block = 170;
int n,m,check[N][block],a[N],w[N],d[N];
vector<int>adj[N];
void dijkstra(){
for(int i = 0; i < n; i++) d[i] = 1e9;
d[a[0]] = 0;
priority_queue<pii,vector<pii>,greater<pii>>pq;
pq.push({0,a[0]});
while(!pq.empty()){
auto[c,u] = pq.top();
pq.pop();
if(c > d[u]) continue;
for(int v: adj[u]){
if(v >= block || (v < block && check[u][v] == 0)){
for(int i = u+v; i < n; i += v){
if(d[i] > d[u]+(i-u)/v){
d[i] = d[u]+(i-u)/v;
pq.push({d[i],i});
}
if(v < block){
if(check[i][v] == 1) break;
check[i][v] = 1;
}
}
for(int i = u-v; i >= 0; i -= v){
if(d[i] > d[u]+(u-i)/v){
d[i] = d[u]+(u-i)/v;
pq.push({d[i],i});
}
if(v < block){
if(check[i][v] == 1) break;
check[i][v] = 1;
}
}
}
}
}
if(d[a[1]] > 9e8) cout << -1;
else cout << d[a[1]];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 0; i < m; i++){
cin >> a[i] >> w[i];
adj[a[i]].push_back(w[i]);
}
for(int i = 0; i < n; i++){
sort(adj[i].begin(),adj[i].end());
adj[i].erase(unique(adj[i].begin(),adj[i].end()),adj[i].end());
}
dijkstra();
}
