#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e4+5, MAX = 2e9;
int n, m, batas;
vector<pair<int, int>> adj[N];
set<int> power[N];
int location[N], p[N];
typedef pair<int, int> state;
int dijkstra(int s, int e) {
vector<bool> vis(n+1, 0);
vector<int> dist(n+1, MAX);
priority_queue<state, vector<state>, greater<state>> pq;
pq.push({0, s});
dist[s] = 0;
while(!pq.empty()) {
int u = pq.top().second; pq.pop();
if(u == e) return dist[e];
if(!vis[u]) {
vis[u] = 1;
for(auto& it : adj[u]) {
int v = it.first, d = it.second;
if(dist[v] > dist[u] + d) {
dist[v] = dist[u] + d;
pq.push({dist[v], v});
}
}
}
}
return -1;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++) {
cin >> location[i] >> p[i];
power[location[i]].insert(p[i]);
}
for(int i = 0; i < n; i++) {
for(auto x : power[i]) {
int lst = -1;
for(int j = i%x; j < n; j+=x) {
if(power[j].count(x) > 0) {
if(lst >= 0) {
adj[lst].push_back({j, abs(lst-j)/x});
adj[j].push_back({lst, abs(lst-j)/x});
}
for(int k = j-x; k > lst; k-=x)
adj[j].push_back({k, abs(k-j)/x});
lst = j;
if(i != j) power[j].erase(x);
} else if(lst >= 0) {
adj[lst].push_back({j, abs(lst-j)/x});
}
}
}
power[i].clear();
}
int ans = dijkstra(location[0], location[1]);
cout << ans << '\n';
return 0;
}
