#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 */
int N, M;
int B[30009], P[30009];
ll dista[30009];
vector<int> pos; // lưu index của các tòa nhà
int id[30009]; // map từ vị trí -> index
const int SQ = 180; // sqrt(30000) ~ 173
struct Node {
ll d;
int u;
bool operator>(const Node& other) const {
return d > other.d;
}
};
void solve() {
cin >> N >> M;
for (int i = 0; i < M; i++) {
cin >> B[i] >> P[i];
id[B[i]] = i;
pos.push_back(B[i]);
}
// Dijkstra
for (int i = 0; i < M; i++) dista[i] = oo;
priority_queue<Node, vector<Node>, greater<Node>> pq;
dista[0] = 0;
pq.push({0, 0});
// visited modulo classes for small P
vector<vector<int>> vis(SQ+5, vector<int>(N+5, 0));
while (!pq.empty()) {
auto [du, u] = pq.top(); pq.pop();
if (du != dista[u]) continue;
if (u == 1) {
cout << du;
return;
}
int step = P[u];
int posu = B[u];
if (step <= SQ) {
int r = posu % step;
if (vis[step][r]) continue;
vis[step][r] = 1;
// duyệt toàn bộ tòa nhà cùng lớp mod
for (int v = 0; v < M; v++) {
if (P[v] && B[v] % step == r) {
ll w = abs(B[v] - posu) / step;
if (dista[v] > du + w) {
dista[v] = du + w;
pq.push({dista[v], v});
}
}
}
} else {
// large step: duyệt trực tiếp theo jump
for (int x = posu + step; x <= N; x += step) {
if (id[x] || id[x]==0) { // tồn tại tòa nhà
int v = id[x];
if (P[v]) {
ll w = (x - posu) / step;
if (dista[v] > du + w) {
dista[v] = du + w;
pq.push({dista[v], v});
}
}
}
}
for (int x = posu - step; x >= 0; x -= step) {
if (id[x] || id[x]==0) {
int v = id[x];
if (P[v]) {
ll w = (posu - x) / step;
if (dista[v] > du + w) {
dista[v] = du + w;
pq.push({dista[v], v});
}
}
}
}
}
}
cout << -1;
}
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
*/
