#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()
#define int long long
const int sz = 1e6 + 1, inf = 1e18;
array<int, 2> a[sz];
int ans = inf, d[sz];
map<array<int, 2>, int> cost;
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;
cost[{i, j}] = abs(a[i][0] - a[j][0]) / a[i][1];
}
}
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 (int u = 1; u < m; u++) {
if (abs(a[v][0] - a[u][0]) % a[v][1] == 0 && d[u] > d[v] + cost[{v, u}]) {
d[u] = d[v] + cost[{v, u}];
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);
}
