#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
ll N,M; cin >> N >> M;
ll K = 9;
ll B[M],P[M];
ll val[N];
ll val2[K][N];
bool found[N];
bool found2[K][N];
vector<pii> doges[N];
for (ll i=0;i<M;i++) {
cin >> B[i] >> P[i];
doges[B[i]].push_back({i,P[i]});
}
for (ll i=0;i<N;i++) {
for (ll k=0;k<K;k++) {
val2[k][i]=1e18;
found2[k][i]=0;
}
val[i]=1e18;
found[i]=0;
}
val[B[0]]=0;
priority_queue<pair<ll,ll>> PQ; //-val, position
priority_queue<array<ll,3>> PQ2; //-val, position, k
PQ.push({0,B[0]});
while(1) {
ll mv = 1e17; ll ctr = -1;
ll lpop = -1;
while (!PQ.empty()) {
pii q0 = PQ.top(); ll v = -q0.first; ll x = q0.second;
if (!found[x]) {
ctr = x; mv = v; lpop = 0;
break;
} else {
PQ.pop();
}
}
while (!PQ2.empty()) {
array<ll,3> a0 = PQ2.top(); ll v = -a0[0]; ll x = a0[1]; ll k = a0[2];
if (v>=mv) {break;}
if (!found2[k][x]) {
found2[k][x]=1;
if (((x-k)>=0)&&(val2[k][x-k]>(1+val2[k][x]))) {
val2[k][x-k]=1+val2[k][x];
PQ2.push({-val2[k][x-k],(x-k),k});
}
if (((x+k)<N)&&(val2[k][x+k]>(1+val2[k][x]))) {
val2[k][x+k]=1+val2[k][x];
PQ2.push({-val2[k][x+k],(x+k),k});
}
if (!found[x]) {
if (val2[k][x]<mv) {
mv = val2[k][x]; ctr = x; lpop = 1;
}
break;
} else {
PQ2.pop();
}
} else {
PQ2.pop();
}
}
if (lpop==-1) {
cout << "-1"; exit(0);
} else if (ctr==B[1]) {
ll ans = val[B[1]];
for (ll k=0;k<K;k++) {
ans = min(ans,val2[k][B[1]]);
}
cout << ans; exit(0);
} else {
if (lpop) {
PQ2.pop();
} else {
PQ.pop();
}
for (pii x0: doges[ctr]) {
ll i = x0.first;
if (P[i]>=K) {
for (ll t=(-(B[i]/P[i]+2));t<(((N-B[i])/P[i])+2);t++) {
if ((B[i]+t*P[i])>=0 && (B[i]+t*P[i])<N) {
if ((mv+(ll)abs(t))<val[(B[i]+t*P[i])]) {
val[(B[i]+t*P[i])]=mv+(ll)abs(t);
PQ.push({-val[(B[i]+t*P[i])],(B[i]+t*P[i])});
}
}
}
} else {
val2[P[i]][B[i]]=mv;
PQ2.push({-mv,B[i],P[i]});
}
}
}
found[ctr]=1;
}
}
