#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
const int N = 30010;
const int oo = 1e8;
using ii = pair<int,int>;
int n, m, st, ft;
vector<int> f[N];
int dist[N];
vector<ii> g[N];
priority_queue<ii, vector<ii>, greater<ii> > q;
bool has(int b, int p) {
int lo = 0, hi = (int)f[b].size() - 1;
while(lo <= hi) {
int mid = (lo + hi) >> 1;
if(f[b][mid] == p) return true;
if(f[b][mid] < p) lo = mid+1;
else hi = mid-1;
} return false;
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 0; i < m; ++i) {
int b, p; scanf("%d %d", &b, &p);
f[b].push_back(p);
if(i == 0) st = b;
else if(i == 1) ft = b;
}
for(int i = 0; i < n; ++i) {
sort(f[i].begin(), f[i].end());
f[i].erase(unique(f[i].begin(),f[i].end()), f[i].end());
}
for(int i = 0; i < n; ++i) {
for(int p : f[i]) {
for(int x = i + p, c = 1; x < n; x += p, ++c) {
g[i].push_back({c, x});
if(has(x,p)) break;
}
for(int x = i - p, c = 1; x >= 0; x -= p, ++c) {
g[i].push_back({c, x});
if(has(x,p)) break;
}
}
}
for(int i = 0; i < n; ++i) dist[i] = oo;
q.push({0,st});
dist[st] = 0;
while(!q.empty()) {
auto U = q.top(); q.pop();
int cw = U.first, u = U.second;
for(auto e : g[u]) {
if(dist[e.second] > cw + e.first) {
dist[e.second] = cw + e.first;
q.push({cw + e.first, e.second});
}
}
}
if(dist[ft] == oo) puts("-1");
else printf("%d\n", dist[ft]);
return 0;
}
