#include <bits/stdc++.h>
using namespace std;
#define N 50001
const int inf = 1e9;
int tc = 1, n, B[N], P[N], m, dis[N], dp[N][500], ans = inf;
vector <int> E[N];
int32_t main() {
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> m;
int sq = 1;
for(int i = 1; i <= 400; i++) {
if(i * i > n) {
sq = i - 1;
break;
}
}
for(int i = 0; i < m; i++) {
cin >> B[i] >> P[i];
E[B[i]].push_back(P[i]);
}
for(int i = 0; i < n; i++) {
dis[i] = inf;
for(int j = 0; j <= 400; j++) {
dp[i][j] = inf;
}
}
priority_queue <tuple<int,int, int>> q;
for(auto i : E[B[0]]) {
if(i <= sq) dp[B[0]][i] = 0;
q.push({0, B[0], i});
}
dis[B[0]] = 0;
while(!q.empty()) {
int pw;
int ind;
int cost;
tie(cost, ind, pw) = q.top();
q.pop();
if(pw < sq) {
if(dp[ind][pw] != -cost) continue;
int np = ind + pw;
if(np < n && dp[np][pw] > dp[ind][pw] + 1) {
dp[np][pw] = dp[ind][pw] + 1;
q.push({-dp[np][pw], np, pw});
for(auto i : E[np]) {
if(i >= sq) {
// if(dis[np] <= dp[ind][pw] + 1) continue;
dis[np] = min(dis[np], dp[ind][pw] + 1);
q.push({-dis[np], np, i});
continue;
}
dp[np][i] = min(dp[np][i], dp[ind][pw] + 1);
q.push({-dp[np][i], np, i});
}
}
np = ind - pw;
if(np >= 0 && dp[np][pw] > dp[ind][pw] + 1) {
dp[np][pw] = dp[ind][pw] + 1;
q.push({-dp[np][pw], np, pw});
for(auto i : E[np]) {
if(i >= sq) {
dis[np] = min(dis[np], dp[ind][pw] + 1);
q.push({-dis[np], np, i});
continue;
}
dp[np][i] = min(dp[np][i],dp[ind][pw] + 1);
q.push({-dp[np][i], np, i});
}
}
}
else {
if(dis[ind] != -cost) continue;
int c = 0;
for(int i = ind + pw; i < n; i += pw) {
c++;
if(dis[i] <= dis[ind] + c) continue;
dis[i] = dis[ind] + c;
for(auto j : E[i]) {
if(j < sq) dp[i][j] = min(dp[i][j], dis[i]);
q.push({-dis[i], i, j});
}
}
c = 0;
for(int i = ind - pw; i >= 0; i -= pw) {
c++;
if(dis[i] <= dis[ind] + c) continue;
dis[i] = dis[ind] + c;
for(auto j : E[i]) {
if(j < sq) dp[i][j] = min(dp[i][j], dis[i]);
q.push({-dis[i], i, j});
}
}
}
}
// cout << dis[B[1]] << endl;
ans = min(ans, dis[B[1]]);
for(int i = 0; i <= 400; i++) {
ans = min(ans, dp[B[1]][i]);
}
cout << (ans == inf ? -1 : ans) << '\n';
return 0;
}
