#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e4 + 5, mod = 1e9 + 7;
const ll inf = 9e18;
int n, m, b[N], p[N], dist[N], u, v, w;
vector <int> luu[N];
queue <pair <pair <int, int>, int>> q;
void pc(int pos) {
dist[pos] = w + 1;
q.push({{pos, v}, dist[pos]});
for (int x : luu[pos]) q.push({{pos, x}, dist[pos]});
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen(".INP", "r", stdin);
// freopen(".OUT", "w", stdout);
cin >> n >> m;
for (int i = 0; i < m; ++i) cin >> b[i] >> p[i], luu[b[i]].push_back(i);
q.push({{0, 0}, 0});
fill(dist + 1, dist + n, n + 1);
while (!q.empty()) {
u = q.front().first.first, v = q.front().first.second, w = q.front().second;
q.pop();
if (dist[u] != w) continue;
for (int pos = u + p[v]; pos < n; pos += p[v]) {
if (dist[pos] == n + 1) {
pc(pos);
break;
}
}
for (int pos = u - p[v]; pos >= 0; pos -= p[v]) {
if (dist[pos] == n + 1) {
pc(pos);
break;
}
}
}
cout << (dist[b[1]] == n + 1 ? -1 : dist[1]);
}
