#include <bits/stdc++.h>
using namespace std;
const int N = (int)3e4, M = (int)3e4;
int n, m;
array<int, 2> doge[M];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
set<int> P;
vector<int> ind;
for(int i = 0;i < m;i ++) {
int b, p;
cin >> b >> p;
P.insert(p);
doge[i] = {b, p};
}
for(auto& e: P) ind.push_back(e);
auto id = [&](int x) {
return lower_bound(ind.begin(), ind.end(), x) - ind.begin();
};
vector<set<int>> pos(n);
for(int i = 0;i < m;i ++) {
pos[doge[i][0]].insert(id(doge[i][1]));
}
vector<vector<pair<int, int>>> adj(n);
set<array<int, 2>> same;
for(int i = 0;i < m;i ++) {
if(same.find(doge[i]) != same.end()) continue;
same.insert(doge[i]);
int it = doge[i][0]+doge[i][1];
int cnt = 1;
while(it < n) {
adj[doge[i][0]].emplace_back(it, cnt);
if(pos[it].find(id(doge[i][1])) != pos[it].end()) break;
it += doge[i][1];
cnt ++;
}
it = doge[i][0]-doge[i][1];
cnt = 1;
while(it >= 0) {
adj[doge[i][0]].emplace_back(it, cnt);
if(pos[it].find(id(doge[i][1])) != pos[it].end()) break;
it -= doge[i][1];
cnt ++;
}
}
vector<int> dist(n, INT_MAX);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, doge[0][0]});
dist[doge[0][0]] = 0;
while((int)pq.size()) {
auto X = pq.top();
pq.pop();
int d, x; tie(d, x) = X;
if(d != dist[x]) continue;
for(auto E : adj[x]) {
int e, w;tie(e, w) = E;
if(dist[e] > dist[x] + w) {
dist[e] = dist[x] + w;
pq.push({dist[e], e});
}
}
}
cout << (dist[doge[1][0]] == INT_MAX ? -1 : dist[doge[1][0]]) << '\n';
return 0;
}
