#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
#define MAX 40100
#define MAXS 20
#define INF 1010101010
#define bb ' '
#define ln '\n'
#define Ln '\n'
vector<pii> adj[MAX];
int B[MAX];
int P[MAX];
vector<int> locset;
vector<int> locs[MAX];
int N, M;
int findpv(int x) {
int ind = upper_bound(locset.begin(), locset.end(), x) - locset.begin();
ind--;
if (ind < 0) return -1;
else return locset[ind];
}
int findnx(int x) {
int ind = lower_bound(locset.begin(), locset.end(), x) - locset.begin();
if (ind >= M) return -1;
else return locset[ind];
}
int np(int x, int p) { return x / p * p + p; }
int dist[MAX];
int vis[MAX];
vector<int> locp[MAX];
bool chk(vector<int>& v, int p) {
int ind = lower_bound(v.begin(), v.end(), p) - v.begin();
if (ind >= v.size() || v[ind] != p) return false;
return true;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> N >> M;
int i;
for (i = 0; i < M; i++) cin >> B[i] >> P[i], locset.emplace_back(B[i]), locs[B[i]].push_back(i), locp[B[i]].push_back(P[i]);
for (i = 0; i < N; i++) sort(locp[i].begin(), locp[i].end());
sort(locset.begin(), locset.end());
locset.erase(unique(locset.begin(), locset.end()), locset.end());
int j;
for (i = 0; i < N; i++) {
for (j = 1; j < locs[i].size(); j++) {
adj[locs[i][j]].emplace_back(locs[i][j - 1], 0);
adj[locs[i][j - 1]].emplace_back(locs[i][j], 0);
}
}
for (i = 0; i < M; i++) {
int delta = 1;
while (1) {
int loc = findpv(B[i] - delta);
if (loc == -1) break;
bool found = false;
if ((B[i] - loc) % P[i] == 0) {
if (chk(locp[loc], P[i])) {
adj[i].emplace_back(locs[loc][0], (B[i] - loc) / P[i]);
found = true;
}
else for (auto v : locs[loc]) adj[i].emplace_back(v, (B[i] - loc) / P[i]);
}
if (found) break;
delta = B[i] - loc;
delta = np(delta, P[i]);
}
delta = 1;
while (1) {
int loc = findnx(B[i] + delta);
if (loc == -1) break;
bool found = false;
if ((loc - B[i]) % P[i] == 0) {
if (chk(locp[loc], P[i])) {
adj[i].emplace_back(locs[loc][0], (loc - B[i]) / P[i]);
found = true;
}
else for (auto v : locs[loc]) adj[i].emplace_back(v, (loc - B[i]) / P[i]);
}
if (found) break;
delta = loc - B[i];
delta = np(delta, P[i]);
}
}
for (i = 1; i < M; i++) dist[i] = INF;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.emplace(0, 0);
while (pq.size()) {
int v = pq.top().second;
pq.pop();
if (vis[v]) continue;
vis[v] = 1;
for (auto& [x, c] : adj[v]) {
if (vis[x]) continue;
if (dist[x] > dist[v] + c) {
dist[x] = dist[v] + c;
pq.emplace(dist[x], x);
}
}
}
if (dist[1] >= INF) dist[1] = -1;
cout << dist[1] << Ln;
}
