#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
// Minimal hash for pair<int, int>
struct H {
size_t operator()(const pair<int, int>& x) const {
return x.first ^ (x.second << 16);
}
};
const int N = 3e4 + 5;
int c[N], p[N];
bool vis_sky[N];
unordered_set<pair<int, int>, H> vis_state;
unordered_set<int> vec[N];
void solve()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> c[i] >> p[i];
vec[c[i]].insert(p[i]);
}
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
pq.push({ 0, c[0], p[0] });
vis_state.insert({ c[0], p[0] });
while (!pq.empty()) {
auto [dist, pos, power] = pq.top();
pq.pop();
if (pos == c[1]) {
cout << dist;
return;
}
if (!vis_sky[pos]) {
vis_sky[pos] = true;
for (int new_p : vec[pos]) {
if (vis_state.find({ pos, new_p }) == vis_state.end()) {
vis_state.insert({ pos, new_p });
pq.push({ dist, pos, new_p });
}
}
}
for (int d : { -1, 1 }) {
int nx = pos + d * power;
if (nx >= 0 && nx < n) {
if (vis_state.find({ nx, power }) == vis_state.end()) {
vis_state.insert({ nx, power });
pq.push({ dist + 1, nx, power });
}
}
}
}
cout << -1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
