#include <queue>
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algos/debug.h"
#else
#define debug(...) 42;
#endif
#define all(x) (x).begin(), (x).end()
#define isz(x) (int)x.size()
const int sz = 1e6 + 1, inf = 1e9;
array<int, 2> a[sz];
int ans = inf, d[sz];
vector<array<int, 2>> g[sz];
void run(int tc) {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> a[i][0] >> a[i][1];
d[i] = inf;
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
if (i == j || abs(a[i][0] - a[j][0]) % a[i][1])
continue;
g[i].push_back({abs(a[i][0] - a[j][0]) / a[i][1], j});
}
}
priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>>
pq;
pq.push({0, 0});
d[0] = 0;
while (!pq.empty()) {
auto [d_v, v] = pq.top();
pq.pop();
if (d_v != d[v])
continue;
for (auto &[w, u] : g[v]) {
if (d[u] > d[v] + w) {
d[u] = d[v] + w;
pq.push({d[u], u});
}
}
}
cout << (d[1] == inf ? -1 : d[1]) << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
for (int tc = 1; tc <= t; tc++)
run(tc);
}
