#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,inline-functions")
#define fi first
#define sc second
const int MAXN = 30000;
const int MAXM = 30000;
bool liberated[MAXN];
int jump[MAXM];
vector<int> in[MAXN];
bitset<MAXM> vis[MAXN];
queue<tuple<int, int, int>> bfs;
int n;
void liberate(int i, int d) {
if (liberated[i]) return;
liberated[i] = true;
for (int v : in[i]) {
if (vis[i][v]) continue;
bfs.push({i, v, d});
vis[i][v] = true;
}
in[i].clear();
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int m; cin >> n >> m;
int pos, pos1, pos0;
for (int i=0; i<m; i++) {
cin >> pos >> jump[i];
if (i == 0) pos0 = pos;
if (i == 1) {
pos1 = pos;
continue;
}
in[pos].push_back(i);
}
liberate(pos0, 0);
while (!bfs.empty()) {
auto [p, v, d] = bfs.front();
// cout << p << ' ' << v << ':' << dist[p][v] << '\n';
bfs.pop();
if (p == pos1) {
cout << d << '\n';
return 0;
}
if (p - jump[v] >= 0 and !vis[p-jump[v]][v]) {
vis[p-jump[v]][v] = true;
bfs.push({p - jump[v], v, d+1});
liberate(p - jump[v], d+ 1);
}
if (p + jump[v] < n and !vis[p+jump[v]][v]) {
vis[p+jump[v]][v] = true;
bfs.push({p + jump[v], v, d + 1});
liberate(p + jump[v], d + 1);
}
}
cout << -1 << '\n';
return 0;
}
