#include <bits/stdc++.h>
#include <queue>
#include <ratio>
using namespace std;
using ll = long long;
const int INF = 1e9 + 12;
const int K = 174;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
//sqrt decomposition + dijkstra?
vector<pair<int, int>> v(m);
for(auto &z : v) {
cin >> z.first >> z.second;
}
vector<pair<int, int>> which[K + 2][K + 2];
for(auto &z : v) {
for(int i = 1; i < K; ++i) {
which[i][z.first % i].push_back(z);
}
}
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
int ans = INF;
pq.push({0, v[0]});
set<pair<int, int>> visited;
// visited.insert(v[0]);
vector<pair<int, int>> where[n];
for(auto z : v) {
where[z.first].push_back(z);
}
while(!pq.empty()) {
auto best = pq.top();
auto current = best.second;
pq.pop();
if(visited.count(current)) continue;
visited.insert(current);
// cerr << best.first << " " << best.second.first << " " << best.second.second << endl;
if(current == v[1]) {
ans = min(ans, best.first);
break;
}
if(current.second == 0) continue;
if(current.second < K) {
for(auto z : which[current.second][current.first % current.second]) {
int raz = abs(z.first - current.first);
raz /= current.second;
if(!visited.count(z)) {
pq.push({best.first + raz, z});
// visited.insert(z);
}
}
which[current.second][current.first % current.second].clear();
} else {
for(int i = current.first; i < n; i += current.second) {
for(auto z : where[i]) {
int raz = abs(z.first - current.first);
raz /= current.second;
if(!visited.count(z)) {
pq.push({best.first + raz, z});
// visited.insert(z);
}
}
where[i].clear();
}
for(int i = current.first - current.second; i >= 0; i -= current.second) {
for(auto z : where[i]) {
int raz = abs(z.first - current.first);
raz /= current.second;
if(!visited.count(z)) {
pq.push({best.first + raz, z});
// visited.insert(z);
}
}
where[i].clear();
}
}
}
cout << ((ans >= INF) ? -1 : ans) << '\n';
}
/*
3 4
2 1
0 1
0 2
2 2
*/
