#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;
int B[MAXN], P[MAXN];
int n, m;
vector <pair <int, int> > ve[MAXN];
set <pair <int, int> > se;
int dist[MAXN];
set <int> E[MAXN];
int main() {
ios_base::sync_with_stdio(false);
cin >> n >> m;
REP(i, m) {
cin >> B[i] >> P[i];
E[B[i]].insert(P[i]);
}
REP(i, n) {
for (int t : E[i]) {
int c = 1;
while (i + t * c < n) {
int j = i + t * c;
ve[i].push_back({j, c});
if (E[j].find(c) != E[j].end()) break;
c++;
}
c = 1;
while (i - t * c >= 0) {
int j = i - t * c;
ve[i].push_back({j, c});
if (E[j].find(c) != E[j].end()) break;
c++;
}
}
}
REP(i, n) dist[i] = 1e9;
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, D = tr.first;
if (x == B[1]) break;
for (auto t : ve[x]) {
int y = t.first, d = t.second;
if (dist[y] > D + d) {
se.erase({dist[y], y});
dist[y] = D + d;
se.insert({dist[y], y});
}
}
}
if (dist[B[1]] >= 1e9) cout << "-1\n";
else cout << dist[B[1]] << "\n";
return 0;
}
