#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,sse4,sse4.2,lzcnt,popcnt")
#include <iostream>
#include<vector>
#include<math.h>
#include<queue>
const int inf = 1e9;
const int tlim = 54e5;
const int sl = 175;
#define f(x, y) x * sl + y
using namespace std;
vector<vector<pair<int, int>>> g; //pos = node,power (= 0 if js node) node*sl+power
priority_queue<pair<int, int>, vector < pair<int, int>>, greater<pair<int, int>>> q; //{dist, pos}
vector<int> dist;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n, m, s = -1, sq, t = -1; cin >> n >> m;
sq = sqrt(n);
int ln = n*sl+sq+5;
g.resize(ln);
dist.assign(ln, inf);
for (int i = 0; i < n; ++i)
for (int j = 1; j <= sq; ++j)
g[f(i, j)].push_back({ sl * i,0 });
for (int i = 0; i < n; ++i)
for (int j = 1; j <= sq; ++j) {
if (i >= j) g[f(i, j)].push_back({ f((i - j), j), 1 });
if ((i + j) < n) g[f(i, j)].push_back({ f((i + j), j), 1 });
}
for (int i = 0; i < m; ++i) {
int x, y; cin >> x >> y;
if (i == 0) s = sl * x;
if (i == 1) t = sl * x;
if (y > sq) {
if (x >= y)
for (int i = x - y, v = 1; i >= 0; i -= y, ++v)
g[sl * x].push_back({ sl * i, v });
if ((x + y) < n)
for (int i = x + y, v = 1; i < n; i += y, ++v)
g[sl * x].push_back({ sl * i, v });
}
else
g[sl * x].push_back({ f(x,y), 0 });
}
dist[s] = 0;
q.push({ 0, s });
while (!q.empty()) {
auto x = q.top(); q.pop();
if (x.second == t) { cout << x.first; return 0; }
for (auto y : g[x.second])
if (dist[y.first] > (x.first + y.second)) {
dist[y.first] = (x.first + y.second);
q.push({ dist[y.first], y.first });
}
}
cout << -1;
}
