#include <bits/stdc++.h>
using namespace std;
#define DIJKSTRA if(d[v] > dist + w) q.push({-(d[v] = dist + w), v})
const int SQRT = 2, MAXN = 3e4, INF = 2e9;
vector<array<int, 2>> g[MAXN*SQRT];
vector<int> h[MAXN];
int n, m, b, p, s, t, d[MAXN*SQRT];
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int _=0; _<m; ++_){
cin >> b >> p;
if(_ == 0) s = b;
if(_ == 1) t = b;
int c = b * SQRT;
if(p < SQRT) g[c].push_back({c+p, 0});
else h[b].push_back(p);
}
priority_queue<array<int, 2>> q;
fill(d, d+n*SQRT, INF);
q.push({d[s*SQRT] = 0, s*SQRT});
while(!q.empty()){
int u = q.top()[1], dist = -q.top()[0];
q.pop();
if(dist != d[u]) continue;
for(auto &[v, w] : g[u]) DIJKSTRA;
int j = u % SQRT, v = u - j, w = 0;
DIJKSTRA;
for(int x : {-1, 1}){
v = u+ x * j * SQRT, w = 1;
if(0<=v && v<n*SQRT) DIJKSTRA;
}
if(j) continue;
b = u / SQRT;
for(int &k : h[b]) for(int i=b%k; i<n; i+=k){
v = i*SQRT, w = abs(b-i)/k;
DIJKSTRA;
}
}
if(d[t*SQRT] == INF) d[t*SQRT] = -1;
cout << d[t*SQRT];
}
