#include <bits/stdc++.h>
using namespace std;
#define oo 1000000000000000000ll
#define int long long
signed main() {
int n, m; cin >> n >> m;
vector<int> b(m), p(m);
for (int i = 0; i < m; ++i) cin >> b[i] >> p[i];
vector<bool> exists(n);
for (int i = 0; i < m; ++i) exists[b[i]] = true;
vector<vector<int>> ed(n, vector<int>(n, oo));
for (int i = 0; i < m; ++i){
int cnt = 0;
for (int j = b[i] + p[i]; j < n; j += p[i]) {
cnt++;
if (exists[j]) ed[b[i]][j] = min(ed[b[i]][j], cnt);
}
for (int j = b[i] - p[i]; j >= 0; j -= p[i]){
cnt++;
if (exists[j]) ed[b[i]][j] = min(ed[b[i]][j], cnt);
}
}
vector<int> d(n, oo); d[b[0]] = 0;
vector<bool> visited(n);
for (int i = 0; i < n; ++i){
int mn = -1;
for (int j = 0; j < n; ++j){
if (!visited[j] && (mn == -1 || d[mn] > d[j])) mn = j;
}
visited[mn] = true;
for (int j = 0; j < n; ++j){
if (visited[j]) continue;
if (d[j] > d[mn] + ed[mn][j]) d[j] = d[mn] + ed[mn][j];
}
}
int ans = d[b[1]];
if (ans == oo) ans = -1;
cout << ans << "\n";
return 0;
}
