#include<bits/stdc++.h>
using namespace std;
#ifdef sus
const int N=100, S=3;
#else
const int N=3e4+10, S=80;
#endif
int n, m, b[N], p[N], heavy[N];
int f[N][S+1];
vector<pair<pair<int, int>, int>> g[N][S+1];
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i=1; i<=m; ++i) cin >> b[i] >> p[i], heavy[i]=p[i]>=S, ++b[i];
for (int i=1; i<=m; ++i) if (heavy[i]){
for (int l=b[i]-p[i], r=b[i]+p[i], cnt=1; l>=1 || r<=n; l-=p[i], r+=p[i], ++cnt){
if (l>=1) g[b[i]][S].push_back({{l, S}, cnt});
if (r<=n) g[b[i]][S].push_back({{r, S}, cnt});
}
for (int j=1; j<S; ++j) g[b[i]][j].push_back({{b[i], S}, 0});
}
for (int i=1; i<=m; ++i) if (!heavy[i]){
for (int j=1; j<=S; ++j) if (j!=p[i]) g[b[i]][j].push_back({{b[i], p[i]}, 0});
}
for (int i=1; i<=n; ++i) for (int j=1; j<S; ++j){
if (i-j>=1) g[i][j].push_back({{i-j, j}, 1});
if (i+j<=n) g[i][j].push_back({{i+j, j}, 1});
}
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
memset(f, 0x3f, sizeof f);
pq.push({f[b[1]][min(S, p[1])]=0, {b[1], min(S, p[1])}});
while (pq.size()){
auto u=pq.top().second;
int d=pq.top().first;
pq.pop();
if (f[u.first][u.second]!=d) continue;
for (auto &e:g[u.first][u.second]){
auto v=e.first; int w=e.second;
if (f[v.first][v.second]>d+w) pq.emplace(f[v.first][v.second]=d+w, v);
}
}
int ans=*min_element(f[b[2]]+1, f[b[2]]+S+1);
if (ans>1e9) ans=-1;
cout << ans << '\n';
return 0;
}
