#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
int32_t main(){
fast
int n, m;
cin >> n >> m;
vector<vector<int> > guy(n);
int st = -1, to = -1;
for(int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
if(st == -1) st = a;
else if(to == -1) to = a;
guy[a].push_back(b);
}
priority_queue <pair<int, int> > pq;
vector <int> dis(n, inf);
dis[st] = 0;
pq.push({0, st});
bitset <200000> calc;
while(!pq.empty()) {
int val = -pq.top().first, node = pq.top().second;
// cout << node << ": \n";
pq.pop();
if(calc[node]) continue;
calc[node] = 1;
for(auto mult:guy[node]) {
// cout << mult << ",\n";
int give = 1;
for(int i = node + mult; i < n; i+=mult, give++) {
if(val + give < dis[i]) {
dis[i] = val + give;
pq.push({-dis[i],i});
// cout << i << "\n";
}
}
give = 1;
for(int i = node - mult; i >= 0; i-=mult, give++) {
if(val + give < dis[i]) {
dis[i] = val + give;
pq.push({-dis[i],i});
// cout << i << "\n";
}
}
}
}
if(dis[to] > 1e8) cout << -1 << "\n";
else cout << dis[to] << "\n";
}
