#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;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
if (!(cin >> N >> M)) return 0;
vector<int> B(M), P(M);
for (int i = 0; i < M; ++i) {
cin >> B[i] >> P[i];
// assume B[i] in [0, N-1]
}
// pos_at[x] = list of doge indices located at position x
vector<vector<int>> pos_at(N);
for (int i = 0; i < M; ++i) pos_at[B[i]].push_back(i);
int SQ = max(1, (int)sqrt(N));
// small[p][r] : for p <= SQ, bucket of doge 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
vector<ll> dist(M, INF);
dist[0] = 0;
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
pq.push({0, 0});
while (!pq.empty()) {
auto cur = pq.top(); pq.pop();
ll du = cur.first;
int u = cur.second;
if (du != dist[u]) continue;
if (u == 1) { // đích là doge index 1
cout << du << '\n';
return 0;
}
int step = P[u];
int posu = B[u];
if (step <= SQ) {
int r = posu % step;
// nếu bucket r chưa bị xử lý, duyệt tất cả phần tử trong bucket
if (!small[step][r].empty()) {
for (int v : small[step][r]) {
ll w = llabs((ll)B[v] - (ll)posu) / step;
if (dist[v] > du + w) {
dist[v] = du + w;
pq.push({dist[v], v});
}
}
// đảm bảo mỗi bucket chỉ xử lý 1 lần
vector<int>().swap(small[step][r]); // clear + free
}
} else {
// large step: duyệt các vị trí posu +/- k*step trong [0, N-1]
for (int x = posu + step; x < N; x += step) {
for (int v : pos_at[x]) {
ll w = (ll)(x - posu) / step;
if (dist[v] > du + w) {
dist[v] = du + w;
pq.push({dist[v], v});
}
}
}
for (int x = posu - step; x >= 0; x -= step) {
for (int v : pos_at[x]) {
ll w = (ll)(posu - x) / step;
if (dist[v] > du + w) {
dist[v] = du + w;
pq.push({dist[v], v});
}
}
}
}
}
cout << -1 << '\n';
return 0;
}
