#include <bits/stdc++.h>
#include <cstdlib>
#include <stdlib.h>
using namespace std;
#define ull unsigned long long
#define ld long double
#define ll long long
#define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
int mod = 1e9 + 7;
const ll inf = 1e18;
const int N = 1e6 + 50, K = 22;
vector<bool> v;
int n, m;
vector<vector<pii>> a;
vector<int> d, p, b;
void dij(int u){
d.assign(n, inf);
p.assign(n, -1);
set<pii> q;
q.insert({0, u});
d[u] = 0;
while(!q.empty()){
int s = q.begin()->second;
int di = q.begin()->first;
q.erase(q.begin());
if(d[s] != di)
continue;
for(auto i : a[s]){
int to = i.first;
int len = i.second;
if(d[s] + len < d[to]){
d[to] = d[s] + len;
p[to] = s;
q.insert({d[to], to});
}
}
}
}
void solve(){
cin >> n >> m;
a = vector<vector<pii>> (n);
b = vector<int> (n, inf);
v = vector<bool> (n, 0);
while(m--){
int x, p;
cin >> x >> p;
if(x == 1)
continue;
b[x] = p;
v[x] = 1;
}
v[1] = 1;
for(int i = 0; i < n; i++){
for(int j = i + b[i]; j < n; j += b[i])
if(v[j])
a[i].push_back({j, (j - i) / b[i]});
for(int j = i - b[i]; j >= 0; j -= b[i])
if(v[j])
a[i].push_back({j, (i - j) / b[i]});
}
dij(0);
// for(auto i : d)
// cout << i << ' ';
// cout << '\n';
cout << d[1] << '\n';
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
// cin >> t;
while(t--)
solve();
return 0;
}
