#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
const int N = 30004;
int b[N];
int seen[N];
vector<int> in[N];
bitset<N> vis[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int p;
cin >> b[i] >> p;
in[b[i]].push_back(p);
}
fill(seen, seen + N, -1);
priority_queue<array<int, 3>> pq;
for (int p : in[b[0]]) {
pq.push({0, p, b[0]});
vis[p][b[0]] = 1;
}
seen[b[0]] = 0;
while (!pq.empty()) {
auto [c, p, v] = pq.top();
c = -c;
if (v == 1) {
cout << c << '\n';
return 0;
}
pq.pop();
int forward = v + p;
if (forward < n && !vis[p][forward]) {
if (seen[forward] == -1) {
seen[forward] = c + 1;
for (int np : in[forward]) {
vis[np][forward] = 1;
pq.push({-(c + 1), np, forward});
}
}
vis[p][forward] = 1;
pq.push({-(c + 1), p, forward});
}
int backward = v - p;
if (backward >= 0 && !vis[p][backward]) {
if (seen[backward] == -1) {
seen[backward] = c + 1;
for (int np : in[backward]) {
vis[np][backward] = 1;
pq.push({-(c + 1), np, backward});
}
}
vis[p][backward] = 1;
pq.push({-(c + 1), p, backward});
}
}
cout << seen[b[1]] << '\n';
return 0;
}
