#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
const int N = 3e5 + 10;
vector<pair<int,int>> adj[N];
vector<int> dog[N];
bool vis[N];
void solve() {
int n, m; cin >> n >> m;
vector<int> b(m), p(m);
int start = -1, endd = -1;
for(int i = 0;i < m; ++i) {
cin >> b[i] >> p[i];
dog[b[i]].pb(i);
if(i == 0) start = b[i];
if(i == 1) endd = b[i];
}
for(int i = 0;i < n; ++i) {
set<int> st;
for(int f: dog[i]) {
int c = p[f];
if(st.count(c)) continue;
st.insert(c);
int pp = i;
int jumps = 0;
while(pp + c < n) {
++jumps;
adj[i].pb({pp + c, jumps});
pp += c;
}
pp = i, jumps = 0;
while(pp - c >= 0) {
++jumps;
adj[i].pb({pp - c, jumps});
pp -= c;
}
}
}
vector<int> dist(N, INT_MAX);
priority_queue<pair<int,int>> q;
q.push({0, start});
dist[start] = 0;
while(!q.empty()) {
int u = q.top().second;
q.pop();
if(vis[u]) continue;
vis[u] = true;
for(auto x: adj[u]) {
int w = x.second, v = x.first;
if(dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
q.push({-dist[v], v});
}
}
}
if(dist[endd] == INT_MAX) cout << "-1\n";
else
cout << dist[endd] << "\n";
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
//cin >> t;
while(t--) {
solve();
}
}
