#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second
using namespace std;
void solve () {
int n, m; cin >> n >> m;
int tx;
vector<int> dis(n, INT_MAX);
vector<set<int>> p(n);
pq<pair<int, int>> q;
for (int i = 0; i < m; i++) {
int x, y; cin >> x >> y;
p[x].insert(y);
if (!i) {dis[x] = 0; q.push({0, x});}
if (i == 1) tx = x;
}
while (!q.empty()) {
auto [d, x] = q.top(); d = -d; q.pop();
if (d != dis[x]) continue;
for (auto j : p[x]) {
for (int i = x + j; i < n; i += j) {
if (!p[i].empty() && d + abs(x - i) / j < dis[i]) {
dis[i] = d + abs(i - x) / j;
q.push({-dis[i], i});
}
if (p[i].find(j) != p[i].end()) break;
}
for (int i = x - j; i >= 0; i -= j) {
if (!p[i].empty() && d + abs(i - x) / j < dis[i]) {
dis[i] = d + abs(i - x) / j;
q.push({-dis[i], i});
}
if (p[i].find(j) != p[i].end()) break;
}
}
}
cout << (dis[tx] == INT_MAX ? -1 : dis[tx]);
}
signed main() {IOS solve(); return 0;}
