#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9+5;
const int MX = 2001;
int n, m;
map<int,int>nodes[MX];
priority_queue<pair<int,int>>pq;
int dist[MX];
bool vis[MX];
vector<int>dvs[MX];
void PlayGround() {
cin >> n >> m;
for(int dv=1; dv<=n; ++dv) {
for(int i=1; dv*i<=n; ++i) {
dvs[dv*i].push_back(dv);
}
}
int b[2];
for(int i=0; i<m; ++i) {
int _b, p;
cin >> _b >> p;
if(i<2) {
b[i] = _b;
}
nodes[_b][p] = 1;
}
for(int i=0; i<n; ++i) {
dist[i] = INF;
}
dist[b[1]] = 0;
pq.emplace(0, b[1]);
while(!pq.empty()) {
int d, v;
tie(d, v) = pq.top();
d = -d;
pq.pop();
if(vis[v]) continue;
vis[v] = 1;
for(int i=0; i<n; ++i) if(i!=v) {
int gap = abs(i-v);
int need = INF;
for(int dv : dvs[gap]) {
if(nodes[i].count(dv)) {
need = min(need, gap/dv);
}
}
if(d+need<dist[i]) {
dist[i] = d+need;
pq.emplace(-dist[i], i);
}
}
}
if(dist[b[0]]==INF) {
dist[b[0]] = -1;
}
cout << dist[b[0]] << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
PlayGround();
return 0;
}
