#include <bits/stdc++.h>
#define hash _hash_
#define left _left_
#define y1 _y1_
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll oo = 1e18;
/*----------- I alone decide my fate! ----------*/
/* Chiec den ong sao, sao 5 canh tuoi mau */
const int MAXM = 30005;
const int SQ = 200;
int N, M;
int a[MAXM], p[MAXM];
ll dista[MAXM];
vector<int> rem[SQ+5][SQ+5]; // rem[j][r] = list of indices có a[i] % j = r
vector<int> pos[30009]; // pos[x] = list of indices có a[i] = x
void Dijkstra(int st, int ed) {
for (int i = 0; i < M; i++) dista[i] = oo;
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
dista[st] = 0;
pq.push({0, st});
int max_a = *max_element(a, a+M);
while (!pq.empty()) {
auto [cost, u] = pq.top(); pq.pop();
if (cost != dista[u]) continue;
if (u == ed) {
cout << cost;
return;
}
if (p[u] <= SQ) {
for (int v : rem[p[u]][a[u] % p[u]]) {
ll w = abs(a[u] - a[v]) / p[u];
if (dista[v] > cost + w) {
dista[v] = cost + w;
pq.push({dista[v], v});
}
}
} else {
for (int x = a[u] % p[u]; x <= max_a; x += p[u]) {
for (int v : pos[x]) {
ll w = abs(a[u] - a[v]) / p[u];
if (dista[v] > cost + w) {
dista[v] = cost + w;
pq.push({dista[v], v});
}
}
}
}
}
cout << -1;
}
void solve() {
cin >> N >> M;
for (int i = 0; i < M; i++) {
cin >> a[i] >> p[i];
for (int j = 1; j <= SQ; j++) {
rem[j][a[i] % j].push_back(i);
}
pos[a[i]].push_back(i);
}
Dijkstra(0, 1); // từ thang máy đầu tiên đến thang máy thứ hai
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
solve();
return 0;
}
/*
How can you see into my eyes, like open doors?
Leading you down into my core, where I've become so numb
Without a soul, my spirit's sleeping somewhere cold
Until you find it here and bring it back home!
Wake me up! Wake me up inside
Cant wake up? Wake me up inside
*/
