#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ld double
#define ll long long
mt19937 rnd(51);
const int N = 30010, K = 50, INF = 1e9, M = 1e5 + 10;
int d[N][K];
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif // LOCAL
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < N; i++) {
for (int j = 0; j < K; j++) {
d[i][j] = INF;
}
}
int n, m;
cin >> n >> m;
vector<int> b(m), p(m), ans(n, INF);
vector<vector<int>> need(n);
for (int i = 0; i < m; i++) {
cin >> b[i] >> p[i];
need[b[i]].pb(abs(p[i]));
}
ans[b[0]] = 0;
set<array<int, 3>> st;
st.insert({0, b[0], -1});
while (st.size() > 0) {
auto arr = *st.begin();
st.erase(arr);
int v = arr[1], j = arr[2];
if (j == -1) {
for (auto to : need[v]) {
if (to < K) {
if (d[v][to] > ans[v]) {
st.erase({d[v][to], v, to});
d[v][to] = ans[v];
st.insert({d[v][to], v, to});
}
} else {
for (int k = v, add = 0; k < n; k += to, add++) {
if (ans[k] > ans[v] + add) {
st.erase({ans[k], k, -1});
ans[k] = ans[v] + add;
st.insert({ans[k], k, -1});
}
}
for (int k = v, add = 0; k >= 0; k -= to, add++) {
if (ans[k] > ans[v] + add) {
st.erase({ans[k], k, -1});
ans[k] = ans[v] + add;
st.insert({ans[k], k, -1});
}
}
}
}
} else {
if (d[v][j] < ans[v]) {
st.erase({ans[v], v, -1});
ans[v] = d[v][j];
st.insert({ans[v], v, -1});
}
if (v + j < n && d[v + j][j] > d[v][j] + 1) {
st.erase({d[v + j][j], v + j, j});
d[v + j][j] = d[v][j] + 1;
st.insert({d[v + j][j], v + j, j});
}
if (v - j >= 0 && d[v - j][j] > d[v][j] + 1) {
st.erase({d[v - j][j], v - j, j});
d[v - j][j] = d[v][j] + 1;
st.insert({d[v - j][j], v - j, j});
}
}
}
cout << (ans[b[1]] == INF ? -1 : ans[b[1]]) << endl;
return 0;
}
