#include <bits/stdc++.h>
using namespace std;
#define bit(i, x) (x >> i & 1)
#define ll long long
#define sz(x) (int)x.size()
const int N = 2e5 + 5;
const int mod = 998244353;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l, ll r) {
return uniform_int_distribution<ll>(l, r)(rng);
}
int n, m;
pair<int, int> S, T;
vector<vector<int>> adj;
vector<vector<int>> d;
deque<pair<int, int>> q;
signed main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
adj.assign(n + 3, vector<int>(0));
for(int i = 1; i <= m; i++) {
int b, p; cin >> b >> p;
adj[b].push_back(p);
if(i == 1) {
S = {b, p};
}
else if(i == 2) {
T = {b, p};
}
}
d.assign(n + 3, vector<int>(n + 3, 1e9));
d[S.first][S.second] = 0;
q.push_back(S);
while(!q.empty()) {
auto [u, k] = q.front();
q.pop_front();
// cout << u << " ";
for(int k2 : adj[u]) {
if(d[u][k2] > d[u][k]) {
d[u][k2] = d[u][k];
q.push_front({u, k2});
}
}
if(u + k <= n - 1 && d[u + k][k] > d[u][k] + 1) {
d[u + k][k] = d[u][k] + 1;
q.push_back({u + k, k});
}
if(u - k >= 0 && d[u - k][k] > d[u][k] + 1) {
d[u - k][k] = d[u][k] + 1;
q.push_back({u - k, k});
}
}
int res = 1e9;
for(int i = 0; i <= n; i++) res = min(res, d[T.first][i]);
if(res == 1e9) res = -1;
cout << res;
// for(int i : adj[1]) cout << i << " ";
return 0 ^ 0;
}
