#include <bits/stdc++.h>
#define hash _hash_
#define left _left_
#define y1 _y1_
using namespace std;
using ll = long long;
const ll oo = (ll)1e18;
const int MAXM = 30009;
int N, M;
int B[MAXM], P[MAXM];
vector<pair<int,ll>> adj[MAXM];
ll dista[MAXM];
void 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 [cost, u] = pq.top();
pq.pop();
if (cost != dista[u]) continue;
if (u == 1) { // đích theo ý bạn (index 1)
cout << cost << '\n';
return;
}
for (auto &e : adj[u]) {
int v = e.first;
ll w = e.second;
if (dista[v] > cost + w) {
dista[v] = cost + w;
pq.push({dista[v], v});
}
}
}
cout << -1 << '\n';
}
void solve() {
cin >> N >> M;
for (int i = 0; i < M; ++i) {
adj[i].clear();
}
// đọc input và tạo danh sách các p xuất hiện
unordered_map<int, vector<int>> sources; // p -> list index i có P[i]==p
sources.reserve(M * 2);
for (int i = 0; i < M; ++i) {
cin >> B[i] >> P[i];
sources[P[i]].push_back(i);
}
// Với mỗi p xuất hiện, nhóm tất cả trạm theo B[j] % p (tất cả j)
for (auto &pr : sources) {
int p = pr.first;
// build groups: rem -> list of indices j (tất cả trạm j)
unordered_map<int, vector<int>> groups;
groups.reserve(M * 2 / max(1, (int)sources.size()));
for (int j = 0; j < M; ++j) {
int rem = B[j] % p;
groups[rem].push_back(j);
}
// cho mỗi nguồn i có P[i]==p, nối đến mọi j trong cùng rem
for (int i_idx : pr.second) {
int rem_i = B[i_idx] % p;
auto &vec = groups[rem_i];
for (int j : vec) {
if (j == i_idx) continue;
ll w = llabs((ll)B[i_idx] - (ll)B[j]) / p; // chia hết vì cùng rem mod p
adj[i_idx].push_back({j, w});
}
}
}
Dijkstra();
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
