#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 = (ll)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];
int id_pos[30009]; // id_pos[position] = index of doge at that position, -1 nếu không có
void solve() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M;
for (int i = 0; i < M; ++i) {
cin >> B[i] >> P[i];
}
// khởi tạo id_pos
for (int i = 0; i <= N; ++i) id_pos[i] = -1;
for (int i = 0; i < M; ++i) {
id_pos[B[i]] = i;
}
// SQ động
int SQ = max(1, (int)sqrt(N));
// Precompute small buckets: for p = 1..SQ, groups of indices j by (B[j] % p)
// small[p][r] => vector of indices j such that B[j] % p == r
vector<vector<vector<int>>> small(SQ + 1);
for (int p = 1; p <= SQ; ++p) {
small[p].assign(p, vector<int>());
}
for (int j = 0; j < M; ++j) {
for (int p = 1; p <= SQ; ++p) {
int r = B[j] % p;
small[p][r].push_back(j);
}
}
// Dijkstra
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[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
auto cur = pq.top(); pq.pop();
ll du = cur.first;
int u = cur.second;
if (du != dista[u]) continue;
if (u == 1) { // đích là doge index 1
cout << du << '\n';
return;
}
int step = P[u];
int posu = B[u];
if (step <= SQ) {
int r = posu % step;
// Nếu bucket đã rỗng => đã xử lý rồi, skip
if (!small[step][r].empty()) {
// duyệt tất cả các node trong bucket
for (int v : small[step][r]) {
ll w = llabs((ll)B[v] - (ll)posu) / step;
if (dista[v] > du + w) {
dista[v] = du + w;
pq.push({dista[v], v});
}
}
// đảm bảo mỗi bucket xử lý đúng 1 lần
small[step][r].clear();
}
} else {
// large step: duyệt theo vị trí thực (những vị trí có doge)
// đi về phải
for (int x = posu + step; x < N; x += step) {
int v = id_pos[x];
if (v != -1) {
ll w = (x - posu) / step;
if (dista[v] > du + w) {
dista[v] = du + w;
pq.push({dista[v], v});
}
}
}
// đi về trái
for (int x = posu - step; x >= 0; x -= step) {
int v = id_pos[x];
if (v != -1) {
ll w = (posu - x) / step;
if (dista[v] > du + w) {
dista[v] = du + w;
pq.push({dista[v], v});
}
}
}
}
}
cout << -1 << '\n';
}
int main() {
solve();
return 0;
}
