#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define MASK(x) (1LL << (x))
#define BIT(x, k) (((x) >> (k)) & 1LL)
#define ALL(x) (x).begin(),(x).end()
#define For(i, a, b) for (int i = (a); i <= (b); ++i)
#define Fod(i, a, b) for (int i = (a); i >= (b); --i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define Fore(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }
template <class U, class V> bool maximize(U &A, const V &B){ return (A < B) ? (A = B, true) : false;}
template <class U, class V> bool minimize(U &A, const V &B){ return (A > B) ? (A = B, true) : false;}
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) { return l + rnd() % (r - l + 1); }
const int MAXN = 2e6 + 5;
int N, M, source, sink;
vector <pair <int, int>> ke[MAXN];
int dp[MAXN];
int ID(int x, int y) {
return (x - 1) * 30 + y;
}
void solve(void) {
cin >> N >> M;
For (i, 1, M) {
int b, q; cin >> b >> q; b++;
if(i == 1) source = b;
if(i == 2) sink = b;
if(q >= 30) {
for (int j = b - q; j >= 1; j -= q) ke[b].push_back(make_pair(j, (b - j) / q));
for (int j = b + q; j <= N; j += q) ke[b].push_back(make_pair(j, (j - b) / q));
} else ke[b].push_back(make_pair(N + ID(b, q), 0));
}
For (i, 1, N) For (j, 1, 30) {
ke[N + ID(i, j)].push_back(make_pair(i, 0));
}
For (i, 1, N) For (j, 1, 30) if(i + j <= N) {
ke[N + ID(i, j)].push_back(make_pair(N + ID(i + j, j), 1));
ke[N + ID(i + j, j)].push_back(make_pair(N + ID(i, j), 1));
}
memset(dp, 0x3f, sizeof(dp));
dp[source] = 0;
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> heap;
heap.push(make_pair(0, source));
while(heap.size()) {
int u = heap.top().second; heap.pop();
for (auto v : ke[u]) if(minimize(dp[v.first], dp[u] + v.second)) {
heap.push(make_pair(dp[v.first], v.first));
}
}
cout << (dp[sink] >= 1e9 ? -1 : dp[sink]);
}
signed main() {
file("TASK");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int test; test = 1;
// cin >> test;
while(test--){
solve();
cout << '\n';
}
// cerr << "Time elapsed: " << TIME << " s.\n";
return (0 ^ 0);
}
