// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
int main() {
ll N,M; cin >> N >> M;
//ll K = 5*floor(sqrt(N+0.001)); //MODIFY
ll K = 10;
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++) {
//val[i]=1e18;
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;
for (ll i=0;i<N;i++) {
if (val[i]<mv && !found[i]) {
mv = val[i]; ctr = i;
}
}
if (ctr==-1) {
cout << "-1"; exit(0);
} else if (ctr==B[1]) {
cout << val[B[1]]; exit(0);
} else {
for (pii x0: doges[ctr]) {
ll i = x0.first;
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) {
val[(B[i]+t*P[i])]=min(val[(B[i]+t*P[i])],mv+(ll)abs(t));
}
}
}
}
found[ctr]=1;
}*/
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];
//cout << "process2: "<<v<<", "<<x<<", "<<k<<"\n";
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();
}
}
//cout << "mv,ctr,lpop="<<mv<<","<<ctr<<","<<lpop<<"\n";
/*for (ll k=0;k<K;k++) {
while (!v2q[k].empty()) {
ll x = v2q[k].top();
if (!found2[k][x] && !found[x]) {
if (val2[k][x]<mv) {
mv = val2[k][x]; ctr = x; lpop = k;
}
break;
} else 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];
v2q[k].push(x-k);
}
if (((x+k)<N)&&(val2[k][x+k]>(1+val2[k][x]))) {
val2[k][x+k]=1+val2[k][x];
v2q[k].push(x+k);
}
}
}
}*/
if (lpop==-1) {
cout << "-1"; exit(0);
} else if (ctr==B[1]) {
//cout << val[B[1]]; exit(0);
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;
}
}
