#include <bits/stdc++.h>
#define hash _hash_
#define left _left_
#define y1 _y1_
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;
/*----------- I alone decide my fate! ----------*/
/* Chiec den ong sao, sao 5 canh tuoi mau */
int N, M;
ll B[30009];
int P[30009];
vector<pair<int,int>> adj[30009]; // adj[u] = {v, weight}
ll dista[30009];
void solve() {
if (!(cin >> N >> M)) return;
for (int i = 0; i < M; ++i) {
cin >> B[i] >> P[i];
}
if (M < 2) { // không có doge 1
cout << -1;
return;
}
// order: tất cả chỉ số doge, sẽ sort theo P, rem = B%P, rồi theo B
vector<int> order(M);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
if (P[i] != P[j]) return P[i] < P[j];
int ri = (int)(B[i] % P[i]);
int rj = (int)(B[j] % P[j]);
if (ri != rj) return ri < rj;
return B[i] < B[j];
});
// duyệt theo từng block có cùng P, trong block tách theo rem rồi nối adjacent
int idx = 0;
while (idx < M) {
int start = idx;
int p = P[order[idx]];
while (idx < M && P[order[idx]] == p) ++idx;
// block [start, idx)
int s = start;
while (s < idx) {
int rem = (int)(B[order[s]] % p);
int t = s + 1;
while (t < idx && (int)(B[order[t]] % p) == rem) ++t;
// indices from s..t-1 have same (p, rem) and are sorted by B because of comparator
for (int k = s; k + 1 < t; ++k) {
int u = order[k];
int v = order[k+1];
ll gap = B[v] - B[u]; // >= 0
ll w = gap / p; // chia hết vì cùng remainder
// thêm cạnh hai hướng
adj[u].push_back({v, (int)w});
adj[v].push_back({u, (int)w});
}
s = t;
}
}
// Dijkstra từ doge 0 tới doge 1
for (int i = 0; i < M; ++i) dista[i] = INF;
using pli = pair<ll,int>;
priority_queue<pli, vector<pli>, greater<pli>> pq;
dista[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
auto cur = pq.top(); pq.pop();
ll d = cur.first;
int u = cur.second;
if (d != dista[u]) continue;
if (u == 1) break; // đã tìm được khoảng cách ngắn nhất tới doge 1
for (auto &e : adj[u]) {
int v = e.first;
ll w = (ll)e.second;
if (dista[v] > d + w) {
dista[v] = d + w;
pq.push({dista[v], v});
}
}
}
if (dista[1] == INF) cout << -1;
else cout << dista[1];
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
/*
Wake me up! Wake me up inside
*/
