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