#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e4 + 30, B = 200;
const int inf = 2e9;
int n, m;
int dist[N][B];
bool bio[N];
vector<int> adj[N];
struct rec {
int d, v, p;
friend bool operator<(const rec& a, const rec& b) {
if (a.d != b.d)
return a.d < b.d;
if (a.v != b.v)
return a.v < b.v;
return a.p < b.p;
}
};
/*
5 3
0 2
1 1
4 1
*/
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
for(int i = 0; i < N; i++) {
for(int j = 0; j < B; j++) {
dist[i][j] = inf;
}
}
cin >> n >> m;
int s = 0, f = 0;
for(int i = 0; i < m; i++) {
int x, k;
cin >> x >> k;
adj[x].push_back(k);
if(i == 0) s = x;
if(i == 1) f = x;
}
// priority_queue<array<int,3>> q;
priority_queue<rec> q;
for(auto x : adj[s]) {
if(x < B) {
dist[s][x] = 0;
q.push({dist[s][x], s, x});
} else {
for(int k = 1; s + k * x < N; k++) {
dist[s + k * x][0] = k;
q.push({-dist[s + k * x][0], s + k * x, 0});
}
for(int k = 1; s - k * x >= 0; k++) {
dist[s - k * x][0] = k;
q.push({-dist[s - k * x][0], s - k * x, 0});
}
}
}
bio[s] = 1;
while(!q.empty()) {
auto top = q.top();
int d = top.d;
int v = top.v;
int p = top.p;
q.pop();
d = -d;
if(d > dist[v][p]) continue;
if(!bio[v]) {
for(auto x : adj[v]) {
if(x < B) {
dist[v][x] = d;
q.push({-dist[v][x], v, x});
} else {
for(int k = 1; v + k * x < n; k++) {
if(dist[v + k * x][0] > d + k) {
dist[v + k * x][0] = d + k;
q.push({-dist[v + k * x][0], v + k * x, 0});
}
}
for(int k = 1; v - k * x >= 0; k++) {
if(dist[v - k * x][0] > d + k) {
dist[v - k * x][0] = d + k;
q.push({-dist[v - k * x][0], v - k * x, 0});
}
}
}
}
bio[v] = 1;
}
if(v + p < N && dist[v + p][p] > d + 1) {
dist[v + p][p] = d + 1;
q.push({-dist[v + p][p], v + p, p});
}
if(v - p >= 0 && dist[v - p][p] > d + 1) {
dist[v - p][p] = d + 1;
q.push({-dist[v - p][p], v - p, p});
}
}
int ans = inf;
for(int k = 0; k < B; k++)
ans = min(ans, dist[f][k]);
if(ans == inf)
ans = -1;
cout << ans << '\n';
return 0;
}
