#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cassert>
#include <tuple>
using namespace std;
const int MAXN = (1 << 15), QUEUE_SIZE = 40000000, CUTOFF = (1 << 8);
vector<int> powers[MAXN];
int dist[MAXN][CUTOFF];
int N, M, S, T;
tuple<int, int, int> qu[QUEUE_SIZE];
int top;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M;
for (int i = 0; i < M; ++i) {
int b, p;
cin >> b >> p;
if (i == 0) S = b;
else if (i == 1) T = b;
powers[b].push_back(p);
if (p >= CUTOFF) powers[b].push_back(-p);
}
for (int i = 0; i < N; ++i) for (int j = 0; j < CUTOFF; ++j) dist[i][j] = QUEUE_SIZE;
qu[0] = make_tuple(S, 0, 0), top = 0;
for (int qi = 0; qi <= top; ++qi) {
int u, d, c;
tie(u, d, c) = qu[qi];
if (u == T) return cout << c << endl, 0;
powers[u].push_back(d);
for (int d0 : powers[u]) {
if (abs(d0) < CUTOFF && dist[u][d0] == QUEUE_SIZE) dist[u][d0] = c;
if (abs(d0) >= CUTOFF) {
if (0 <= u + d0 && u + d0 < N) qu[++top] = make_tuple(u + d0, d0, c + 1);
} else {
if (u - d0 >= 0 && dist[u - d0][d0] == QUEUE_SIZE) {
qu[++top] = make_tuple(u - d0, d0, dist[u - d0][d0] = c + 1);
}
if (u + d0 < N && dist[u + d0][d0] == QUEUE_SIZE) {
qu[++top] = make_tuple(u + d0, d0, dist[u + d0][d0] = c + 1);
}
}
}
powers[u].clear();
}
cout << -1 << endl;
}
