#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<int> B(M), P(M);
for (int i = 0; i < M; i++) {
cin >> B[i] >> P[i];
}
vector<vector<int>> doges_at(N); // binodagi dogelar
for (int i = 0; i < M; i++) {
doges_at[B[i]].push_back(i);
}
int tot = N + M;
vector<int> dist(tot, INF);
deque<int> dq;
dist[N + 0] = 0; // doge 0 dan boshlaymiz
dq.push_back(N + 0);
vector<bool> used(N, false); // binoda faqat bir marta uzatamiz
while (!dq.empty()) {
int u = dq.front(); dq.pop_front();
if (u >= N) {
// bu doge
int j = u - N;
int b = B[j], p = P[j];
for (int d = -1; d <= 1; d += 2) {
int nb = b + d * p;
if (nb >= 0 && nb < N && dist[nb] > dist[u] + 1) {
dist[nb] = dist[u] + 1;
dq.push_back(nb);
}
}
} else {
// bu bino
if (used[u]) continue;
used[u] = true;
for (int j : doges_at[u]) {
int v = N + j;
if (dist[v] > dist[u]) {
dist[v] = dist[u];
dq.push_front(v);
}
}
}
}
int res = dist[N + 1];
cout << (res == INF ? -1 : res) << "\n";
return 0;
}
