#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
const int N = 30004;
int seen[N];
vector<int> in[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 v, p;
cin >> v >> p;
in[v].push_back(p);
}
fill(seen, seen + N, -1);
set<pair<int, int>> vis;
priority_queue<array<int, 3>> pq;
for (int p : in[0]) {
pq.push({0, p, 0});
vis.emplace(p, 0);
}
seen[0] = 0;
while (!pq.empty()) {
auto [c, p, v] = pq.top();
c = -c;
//deb(p) deb(c) deb(v) cout << endl;
//assert(v >= 0);
pq.pop();
int forward = v + p;
if (forward < n && !vis.count({p, forward})) {
if (seen[forward] == -1) {
seen[forward] = c + 1;
for (int np : in[forward]) {
vis.emplace(np, forward);
pq.push({-(c + 1), np, forward});
}
}
vis.emplace(p, forward);
pq.push({-(c + 1), p, forward});
}
int backward = v - p;
if (backward >= 0 && !vis.count({p, backward})) {
if (seen[backward] == -1) {
seen[backward] = c + 1;
for (int np : in[backward]) {
vis.emplace(np, backward);
pq.push({-(c + 1), np, backward});
}
}
vis.emplace(p, backward);
pq.push({-(c + 1), p, backward});
}
}
cout << seen[1] << '\n';
return 0;
}
