#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> X(m), P(m);
for (int i = 0; i < m; i++)
cin >> X[i] >> P[i];
vector<int> dis(n, INT_MAX); dis[X[0]] = 0;
priority_queue<pair<int, pair<int, int>>> q; q.push({0, {X[0], P[0]}});
while (!q.empty()) {
int d = q.top().first;
auto [x, p] = q.top().second; q.pop();
if (x == X[1]) return cout << dis[x], 0;
if (-d != dis[x]) continue;
for (int i = x; i >= 0; i -= p) {
for (int j = 0; j < m; j++) {
if (!(abs(X[j] - i) % P[j]) && dis[x] + (x - i) / p + abs(X[j] - i) / P[j] < dis[i]) {
dis[i] = dis[x] + (x - i) / p + abs(X[j] - i) / P[j];
q.push({-dis[i], {i, P[j]}});
}
}
}
for (int i = x; i < n; i += p) {
for (int j = 0; j < m; j++) {
if (!(abs(X[j] - i) % P[j]) && dis[x] + (i - x) / p + abs(X[j] - i) / P[j] < dis[i]) {
dis[i] = dis[x] + (i - x) / p + abs(X[j] - i) / P[j];
q.push({-dis[i], {i, P[j]}});
}
}
}
}
cout << -1;
}
