// In the name of God
// Hope is last to die
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define int long long
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
const int maxn = 3e4 + 5;
const int inf = 1e9 + 7;
int n, m, s, t, d[maxn];
vector<int> vec[maxn];
vector<pii> adj[maxn];
bool mark[maxn];
set<pll> st;
void dij(){
memset(d, 63, sizeof d);
d[s] = 0;
st.insert(mp(0, s));
while(st.size()){
int v = (*st.begin()).S, dist = (*st.begin()).F;
st.erase(st.begin());
for(auto [u, w]: adj[v]){
if(d[u] > dist + w){
st.erase(mp(d[u], u));
d[u] = dist + w;
st.insert(mp(d[u], u));
}
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++){
int b, p; cin >> b >> p;
if(p < n) vec[p].pb(b);
if(i == 0) s = b;
if(i == 1) t = b;
}
for(int p = 1; p < n; p++){
for(auto u: vec[p]) mark[u] = 1;
for(int i = 0; i < n; i++){
if(!mark[i]) continue;
for(int j = i - p; j >= 0; j -= p){
adj[i].pb(mp(j, (i - j) / p));
if(mark[j]) break;
}
for(int j = i + p; j < n; j += p){
adj[i].pb(mp(j, (j - i) / p));
if(mark[j]) break;
}
}
for(auto u: vec[p]) mark[u] = 0;
}
dij();
if(d[t] >= inf) cout << -1 << '\n';
else cout << d[t] << '\n';
return 0;
}
