// fikhshal chye daram code miznm :}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
const int maxn5 = 2e3 + 10;
const int maxn = 3e4 + 10;
int a[maxn], p[maxn], per[maxn];
int dis[maxn];
vector <pair<int, int>> adj[maxn];
bool mark[maxn];
map <int, int> last[maxn];
inline bool cmp(int i, int j){return a[i] < a[j];}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n, m; cin >> n >> m;
for(int i = 0; i < m; i++){
cin >> a[i] >> p[i];
per[i] = i;
}
sort(per, per + m); // bar hasbe a
for(int i = 0; i < m; i++){
int id = per[i];
int l = a[id] % p[id], ind = -1;
if(last[p[id]].find(a[id] % p[id]) != last[p[id]].end()){
ind = last[p[id]][a[id] % p[id]];
l = a[ind];
}
for(int j = l; j < min(n, a[id] + 1); j += p[id]){
adj[a[id]].pb({j, (a[id] - j) / p[id]});
if(ind != -1)
adj[a[ind]].pb({j, (j - a[ind]) / p[id]});
}
last[p[id]][a[id] % p[id]] = id;
}
for(int i = 0; i < n; i++) for(auto it = last[i].begin(); it != last[i].end(); it++){
int id = (it -> se);
for(int k = a[id] + p[id]; k < n; k += p[id])
adj[a[id]].pb({k, (k - a[id]) / p[id]});
}
memset(dis, -1, sizeof dis);
dis[a[0]] = 0;
for(int tt = 0; tt < n; tt++){
int v = -1;
for(int i = 0; i < n; i++) if(!mark[i] && dis[i] != -1 && (v == -1 || dis[i] < dis[v]))
v = i;
if(v == -1 || v == a[1])
break;
mark[v] = true;
for(auto [u, w] : adj[v]) if(!mark[u] && (dis[u] == -1 || dis[v] + w < dis[u]))
dis[u] = dis[v] + w;
}
cout << dis[a[1]] << endl;
}
/*
5 3
0 2
1 1
4 1
*/
