#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;
const int MAXN = 30010;
ll B[MAXN], P[MAXN];
int n, m;
vector <pair <int, ll> > ve[MAXN];
set <pair <ll, int> > se;
ll dist[MAXN];
int bio[MAXN];
int main() {
ios_base::sync_with_stdio(false);
cin >> n >> m;
REP(i, m) cin >> B[i] >> P[i];
REP(i, m) {
REP(j, n) {
if (abs(B[i] - j) % P[i] == 0) ve[B[i]].push_back({j, abs(B[i] - j) / P[i]});
}
}
REP(i, n) dist[i] = (1LL << 60);
dist[B[0]] = 0;
REP(i, n) se.insert({dist[i], i});
while (se.size()) {
auto tr = *se.begin();
se.erase(se.begin());
int x = tr.second;
ll D = tr.first;
bio[x] = 1;
if (x == B[1]) continue;
for (auto t : ve[x]) {
int y = t.first;
ll d = t.second;
if (dist[y] > D + d) {
assert(bio[y] == 0);
se.erase({dist[y], y});
dist[y] = D + d;
se.insert({dist[y], y});
}
}
}
if (dist[B[1]] >= (1LL << 60)) cout << "-1\n";
else cout << dist[B[1]] << "\n";
return 0;
}
