#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
//#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 998244353;
const int inf = 1e9;
void solve() {
int n, m; cin >> n >> m;
vector<int> b(m), p(m);
rep(i, 0, m)
cin >> b[i] >> p[i];
int d[n][n];
rep(i, 0, n)
rep(j, 0, n)
d[i][j] = inf;
//vector<P> g[n+1];
rep(i, 0, m) {
//g[b[i]].push_back(P(i, 0));
d[b[i]][b[i]] = 0;
int x = b[i]-p[i], y = 1;
while (x >= 0) {
//g[x].push_back(P(i, y++));
d[b[i]][x] = min(d[b[i]][x], y++);
x -= p[i];
}
x = b[i]+p[i], y = 1;
while (x < n) {
//g[x].push_back(P(i, y++));
d[b[i]][x] = min(d[b[i]][x], y++);
x += p[i];
}
}
vector<P> g[n];
rep(i, 0, n)
rep(j, 0, n)
if (d[i][j] != inf)g[i].push_back(P(j, d[i][j]));
vector<int> vis(n, inf);
priority_queue<P, vector<P>, greater<P>> pq;
pq.push({0, b[0]}); vis[b[0]] = 0;
while (!pq.empty()) {
auto [dt, nd] = pq.top(); pq.pop();
if (vis[nd] != dt)continue;
for (auto [i, w]: g[nd]) {
if (dt+w < vis[i])
vis[i] = dt+w,
pq.push({vis[i], i});
}
}
if (vis[b[1]] == inf)cout << -1 << nl;
else cout << vis[b[1]] << nl;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
