#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n, m; cin >> n >> m;
vector<int> b(m + 1), p(m + 1);
vector<vector<int>> vc(n + 1);
vector<vector<i64>> dis(n + 1, vector<i64>(205, 1e18));
for(int i = 1; i <= m; ++i) cin >> b[i] >> p[i], vc[b[i]].push_back(p[i]);
dis[b[1]][0] = 0;
priority_queue<tuple<i64, int, int>, vector<tuple<i64, int, int>>, greater<tuple<i64, int, int>>> pq;
pq.emplace(0, b[1], 0);
while(!pq.empty()){
auto [d, u, pw] = pq.top(); pq.pop();
if(dis[u][pw] < d) continue;
if(!pw){
for(auto x:vc[u]){
if(x >= 200){
int ct = 1;
for(int i = u + x; i < n; i += x){
if(dis[i][0] > d + ct){
dis[i][0] = d + ct;
pq.emplace(dis[i][0], i, 0);
}
ct++;
}
ct = 1;
for(int i = u - x; i >= 0; i -= x){
if(dis[i][0] > d + ct){
dis[i][0] = d + ct;
pq.emplace(dis[i][0], i, 0);
}
ct++;
}
}
else{
if(dis[u][x] > d){
dis[u][x] = d;
pq.emplace(dis[u][x], u, x);
}
}
}
}
else{
if(u - pw >= 0) if(dis[u - pw][pw] > d + 1){dis[u - pw][pw] = d + 1; pq.emplace(d + 1, u - pw, pw);}
if(u + pw < n) if(dis[u + pw][pw] > d + 1){dis[u + pw][pw] = d + 1; pq.emplace(d + 1, u + pw, pw);}
if(dis[u][0] > d){
dis[u][0] = d;
pq.emplace(d, u, 0);
}
}
}
dis[b[2]][0] == 1e18 ? cout << -1 << '\n' : cout << dis[b[2]][0] << '\n';
}
