#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define f first
#define s second
const int MAX = 30005;
const int SQRT = 125;
const int INF = 1000000000;
int p[MAX], len[MAX]; // position, length
vector<pair<pii, int> > g[MAX][SQRT];
vector<int> powers[MAX]; // powers of doges at a given position
int dist[MAX][SQRT];
priority_queue<pair<int, pair<int, int> > > pq;
int xd = 0;
void dijk(int i, int j) {
dist[i][j] = 0;
//cout << i << " " << j << " " << 0 << endl;
pq.push({0, {i, j}});
while (!pq.empty()) {
xd += 1;
auto top = pq.top(); pq.pop();
int d = -top.f;
pair<int, int> loc = top.s;
if (d > dist[loc.f][loc.s]) {
continue;
}
//cout << loc.f << " " << loc.s << endl;
for (auto i : g[loc.f][loc.s]) {
//cout << i.f.f << " " << i.f.s << endl;
int d_new = (d + i.s);
if (d_new < dist[i.f.f][i.f.s]) {
dist[i.f.f][i.f.s] = d_new;
//cout << "came from: " << loc.f << " " << loc.s << endl;
//cout << i.f.f << " " << i.f.s << " " << d_new << endl;
pq.push({-d_new, i.f});
}
}
}
}
int main() {
//freopen("a.in", "r", stdin);
//freopen("a.out", "w", stdout);
for (int i=0; i<MAX; i++) {
for (int j=0; j<SQRT; j++) {
dist[i][j] = INF;
}
}
int n, m; scanf("%d %d", &n, &m);
for (int i=0; i<m; i++) {
scanf("%d %d", &p[i], &len[i]);
powers[p[i]].push_back(len[i]);
}
for (int i=0; i<n; i++) {
for (int j=1; j<SQRT; j++) {
g[i][j].push_back({{i, 0}, 0});
}
for (int j : powers[i]) {
if (j < SQRT) {
g[i][0].push_back({{i, j}, 0});
}
}
}
for (int i=0; i<m; i++) {
if (len[i] > SQRT) {
for (int j=p[i]+len[i]; j<n; j+=len[i]) {
g[p[i]][0].push_back({{j, 0}, (j-p[i])/len[i]});
}
for (int j=p[i]-len[i]; j>=0; j-=len[i]) {
g[p[i]][0].push_back({{j, 0}, (p[i]-j)/len[i]});
}
}
}
for (int i=0; i<n; i++) {
for (int j=1; j<SQRT; j++) {
if (i-j >= 0) { g[i][j].push_back({{i-j, j}, 1}); }
if (i+j < n) { g[i][j].push_back({{i+j, j}, 1}); }
}
}
/*
int ct = 0;
for (int i=0; i<MAX; i++) {
for (int j=0; j<SQRT; j++) {
ct += g[i][j].size();
}
}
cout << ct << endl;
*/
dijk(p[0], 0);
if (dist[p[1]][0] == INF) { printf("%d\n", -1); }
else { printf("%d\n", dist[p[1]][0]); }
//cout << xd << endl;
}
