#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
#define all(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9;
const int MXN = 3e4+4;
vector<pii> g[MXN];
int dis[MXN];
int n, m, B[MXN], P[MXN];
set<int> st[MXN];
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+n, 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];
}
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> m;
for(int i=0; i<m; i++) {
cin >> B[i] >> P[i];
st[B[i]].insert(P[i]);
}
for(int i=0; i<n; i++)
for(int p : st[i]) {
int cost = 0;
for(int j=i+p; j<n; j+=p) {
add_edge(i, j, ++cost);
if(st[j].find(p) != st[j].end()) break;
}
cost = 0;
for(int j=i-p; j>=0; j-=p) {
add_edge(i, j, ++cost);
if(st[j].find(p) != st[j].end()) break;
}
}
int ans = dijkstra(B[0], B[1]);
if(ans == INF) ans = -1;
cout << ans << '\n';
return 0;
}
