#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,sse4,sse4.2,lzcnt,popcnt")
#define X first
#define Y second
#define SZ(x) int(x.size())
#define pb push_back
#define Mp make_pair
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9;
const int MXN = 3e4+4;
const int MX = 5220004;
vector<pii> g[MX];
int dis[MX];
inline void add_edge(int u, int v, int w) {
g[u].pb(pii(v,w));
}
inline int dijkstra(int s, int t) {
fill(dis, dis+MX, INF);
dis[s] = 0;
priority_queue<pii> pq;
pq.push(pii(0, s));
while(!pq.empty()) {
int d = -pq.top().X, v = pq.top().Y;
pq.pop();
if(d!=dis[v]) continue;
for(auto [u, w] : g[v])
if(dis[u]>d+w)
pq.push(pii(-(dis[u]=d+w), u));
}
return dis[t];
}
int n, m, sq, B[MXN], P[MXN];
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> m;
sq=1; while(sq*(sq++)<=n); sq--;
for(int i=0; i<n; i++)
for(int p=1; p<=sq; p++) {
if(i-p>=0) {
add_edge(p*n+i, p*n+i-p, 1);
add_edge(p*n+i, i-p, 1);
}
if(i+p<n) {
add_edge(p*n+i, p*n+i+p, 1);
add_edge(p*n+i, i+p, 1);
}
}
for(int i=0; i<m; i++) {
cin >> B[i] >> P[i];
if(P[i]<=sq) add_edge(B[i], P[i]*n+B[i], 0);
else {
for(int j=B[i]%P[i]; j<n; j+=P[i])
if(i^j)
add_edge(B[i], j, abs(B[i]-j)/P[i]);
}
}
int ans = dijkstra(B[0], B[1]);
if(ans == INF) ans = -1;
cout << ans << '\n';
return 0;
}
