#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cassert>
using namespace std;
const int MAXN = (1 << 15), QUEUE_SIZE = 40000000;
vector<int> powers[MAXN];
unordered_map<int, int> dist[MAXN];
int N, M, S, T;
int qu[QUEUE_SIZE], 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);
}
qu[0] = S * MAXN, top = 0;
for (int qi = 0; qi <= top; ++qi) {
int u = qu[qi] / MAXN, d = qu[qi] & (MAXN - 1), c = dist[u][d];
if (u == T) return cout << c << endl, 0;
powers[u].push_back(d);
for (int d0 : powers[u]) {
if (dist[u].find(d0) == dist[u].end()) dist[u][d0] = c;
if (u - d0 >= 0 && dist[u - d0].find(d0) == dist[u - d0].end()) {
qu[++top] = (u - d0) * MAXN + d0;
dist[u - d0][d0] = c + 1;
}
if (u + d0 >= 0 && dist[u + d0].find(d0) == dist[u + d0].end()) {
qu[++top] = (u + d0) * MAXN + d0;
dist[u + d0][d0] = c + 1;
}
}
powers[u].clear();
}
cout << -1 << endl;
}
