#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <time.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef double lf;
const int N_ = 30050;
const int M_ = 30050;
vector<int> jumps[N_];
int N, M;
int target, ans;
int start;
int dst[N_];
bool vis[N_];
void solve1() {
for(int i = 0; i < N; i++) dst[i] = (int)1e9;
dst[start] = 0;
for(int rep = 0; rep < N; rep++) {
int u = -1, d = (int)1e9;
for(int i = 0; i < N; i++) {
if(dst[i] < d && !vis[i]) u = i, d = dst[i];
}
if(u == -1) {
ans = -1;
return;
}
if(u == target) {
ans = d;
return;
}
vis[u] = true;
for(int e = 0; e < jumps[u].size(); e++) {
int p = jumps[u][e];
for(int i = u + p, j = 1; i < N; i += p, j++) {
if(!vis[i] && dst[i] > dst[u] + j) dst[i] = dst[u] + j;
}
for(int i = u - p, j = 1; i >= 0; i -= p, j++) {
if(!vis[i] && dst[i] > dst[u] + j) dst[i] = dst[u] + j;
}
}
}
}
void solve2() {
}
int main() {
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
scanf("%d%d", &N, &M);
for(int i = 0; i < M; i++) {
int b, p;
scanf("%d%d", &b, &p);
if(i == 0) start = b;
if(i == 1) target = b;
if(p < N) jumps[b].push_back(p);
}
if(N <= 2000) {
solve1();
}else{
solve2();
}
printf("%d\n", ans);
return 0;
}
