#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 30000
const int inf = 1e10;
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 = sqrt(n);
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;
}
priority_queue <tuple<int,int, int>> q;
for(int i = 0; i < n; i++) {
for(int j = 0; j <= 200; j++) {
dp[i][j] = inf;
}
}
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();
// cout << ind << " " << pw << " " << cost << endl;
if(pw <= sq) {
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]) {
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]) {
dp[np][i] = min(dp[np][i],dp[ind][pw] + 1);
q.push({-dp[np][i], np, i});
}
}
}
else {
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]) {
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]) {
q.push({-dis[i], i, j});
}
}
}
}
ans = min(ans, dis[B[1]]);
for(int i = 0; i <= 200; i++) {
ans = min(ans, dp[B[1]][i]);
}
cout << (ans == inf ? -1 : ans) << '\n';
return 0;
}
