#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 500005
const int inf = 1e18;
int tc = 1, n, B[N], P[N], m, dis[N];
vector <int> E[N];
int32_t main() {
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++) {
cin >> B[i] >> P[i];
E[B[i]].push_back(P[i]);
}
for(int i = 0; i < n; i++) {
dis[i] = inf;
}
priority_queue <tuple<int,int, int>> q;
q.push({0, B[0], P[0]});
dis[B[0]] = 0;
while(!q.empty()) {
int pw;
int ind;
tie(ignore, ind, pw) = q.top();
q.pop();
// cout << ind <<" " << pw << '\n';
int c = 0;
for(int i = ind + pw; i < n; i += pw) {
c++;
if(dis[i] <= dis[ind] + c) {
continue;
}
dis[i] = dis[ind] + c;
for(auto j : E[i]) {
q.push({-dis[i], i, j});
}
}
c = 0;
for(int i = ind - pw; i >= 0; i -= pw) {
c++;
if(dis[i] <= dis[ind] + c) continue;
dis[i] = dis[ind] + c;
for(auto j : E[i]) {
q.push({-dis[i], i, j});
}
}
}
cout << dis[B[1]] << '\n';
return 0;
}
