/**
* author: NimaAryan
* created: 2023-11-17 08:21:07
**/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#endif
using i64 = long long;
int 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>> at(N);
for (int i = 0; i < M; ++i) {
at[B[i]].push_back(P[i]);
}
constexpr int inf = numeric_limits<int>::max();
vector<int> dist(N, inf);
dist[B[1]] = 0;
vector<bool> vis(N);
for (int it = 0; it < N; ++it) {
int v = -1;
for (int u = 0; u < N; ++u) {
if (!vis[u] && (v == -1 || dist[u] < dist[v])) {
v = u;
}
}
if (v == -1 || dist[v] == inf) {
break;
}
vis[v] = true;
for (int u = 0; u < N; ++u) {
if (vis[u]) {
continue;
}
int d = abs(v - u);
for (int p : at[u]) {
if (d % p == 0) {
dist[u] = min(dist[u], dist[v] + d / p);
}
}
}
}
cout << (vis[B[0]] ? dist[B[0]] : -1) << "\n";
return 0;
}
