#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int nax = 30 * 1000 + 10, B = 200, INF = 1e9 + 10;
int n, m;
int jump[nax], pos[nax];
vector<pi>V[nax];
bool exists[nax][B + 10];
int dist[nax][B + 10];
priority_queue<pair<int, pi>>PQ;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i < n; ++i) {
for(int j = 0; j <= B; ++j) {
dist[i][j] = INF;
}
}
for(int i = 1; i <= m; ++i) {
cin >> pos[i] >> jump[i];
if(jump[i] > B) {
for(int j = 1; j * jump[i] + pos[i] < n; ++j) {
V[pos[i]].emplace_back(j * jump[i] + pos[i], j);
}
for(int j = -1; j * jump[i] + pos[i] >= 0; --j) {
V[pos[i]].emplace_back(j * jump[i] + pos[i], -j);
}
} else {
exists[pos[i]][jump[i]] = true;
}
}
dist[pos[1]][jump[1]] = 0;
PQ.push({0, {pos[1], jump[1]}});
while(!PQ.empty()) {
auto [x, y] = PQ.top();
PQ.pop();
if(-x > dist[y.ST][y.ND]) continue;
if(y.ST == pos[2]) {
cout << -x;
return 0;
}
if(y.ND == 0) {
for(auto nbh : V[y.ST]) {
if(dist[nbh.ST][0] > -x + nbh.ND) {
dist[nbh.ST][0] = -x + nbh.ND;
PQ.push({-dist[nbh.ST][0], {nbh.ST, 0}});
}
}
for(int i = 1; i <= B; ++i) {
if(exists[y.ST][i] && dist[y.ST][i] > -x) {
dist[y.ST][i] = -x;
PQ.push({-dist[y.ST][i], {y.ST, i}});
}
}
} else {
if(dist[y.ST][0] > -x) {
dist[y.ST][0] = -x;
PQ.push({x, {y.ST, 0}});
}
for(int d : {-y.ND, y.ND}) {
if(y.ST + d < n && y.ST + d >= 0) {
if(dist[y.ST + d][y.ND] > -x + 1) {
dist[y.ST + d][y.ND] = -x + 1;
PQ.push({-(-x + 1), {y.ST + d, y.ND}});
}
}
}
}
}
cout << "-1";
}
