#include <bits/stdc++.h>
#include <bits/stdc++.h>
#include <iomanip>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,sse4")
using namespace std;
# define pb push_back
# define pf push_front
# define ff first
# define ss second
# define ll long long
# define lc id * 2
# define rc lc | 1
//# define int long long
# define mid (r + l) / 2
//# define mp make_pair
typedef long double ld;
#define kill(x) cout << x << '\n', exit(0)
typedef pair<int, char> pic;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef priority_queue<pll, vector<pll>, greater<pll>> pq;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn = 3e4 + 10, maxm = 4e5 + 10, sq = 1300, LOG = 30, mod = 1e9 + 7;
const ll inf = 1e17;
int n, m;
int p[maxn], b[maxn];
vector<int> e[maxn];
ll dist[maxn];
pq vals;
void dijk(int st){
dist[st] = 0;
vals.push({0, st});
while(! vals.empty()){
auto [d, v] = vals.top();
vals.pop();
if(d > dist[v]) continue;
if(v == b[1]) break;
for(int x : e[v]){
int step = 0;
for(int i = v + x; i < n; i += x){
step ++;
if(dist[v] + step >= dist[i]) continue;
dist[i] = dist[v] + step;
vals.push({dist[i], i});
}
step = 0;
for(int i = v - x; i >= 0; i -= x){
step ++;
if(dist[v] + step >= dist[i]) continue;
dist[i] = dist[v] + step;
vals.push({dist[i], i});
}
}
}
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i ++){
cin >> b[i] >> p[i];
e[b[i]].pb(p[i]);
}
for(int i = 0; i < n; i ++){
sort(e[i].begin(), e[i].end());
e[i].resize(unique(e[i].begin(), e[i].end()) - e[i].begin());
}
memset(dist, 63, sizeof(dist));
dijk(b[0]);
cout << (dist[b[1]] >= inf ? -1 : dist[b[1]]) << '\n';
return 0;
}
