#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define p_q priority_queue
#define MN 1000000009
int n, m, P, D, X, K, t, p[30005], j[30005], d[30005][105], J;
p_q<pair<int, pii> > pq;
bool u[30005][105];
vector<int> v[30005];
int main(){
memset(d, 0x3f3f3f3f, sizeof d);
scanf("%i%i", &n, &m);
for (int l=0; l<m; ++l){
scanf("%i%i", &p[l], &j[l]);
v[p[l]].pb(j[l]);
}
X=p[1];
pq.push(mp(0, mp(p[0], 0))); d[p[0]][0]=0;
while(!pq.empty()){
P=pq.top().y.x; K=pq.top().y.y; pq.pop();
if (u[P][K]) continue;
u[P][K]=1;
if (d[P][K]<d[P][0]){
d[P][0]=d[P][K];
pq.push(mp(-d[P][K], mp(P, 0)));
}
//cout << P << ' ' << d[P] << endl;
if (P==X){
cout << d[P][K]; return 0;
}
if (K>0){
if (P-K>=0){
if (d[P][K]+1<d[P-K][K]){
d[P-K][K]=d[P][K]+1; pq.push(mp(-d[P][K]-1, mp(P-K, K)));
}
}
if (P+K<=n){
if (d[P][K]+1<d[P+K][K]){
d[P+K][K]=d[P][K]+1; pq.push(mp(-d[P][K]-1, mp(P+K, K)));
}
}
continue;
}
for (int l2=0; l2<v[P].size(); ++l2){
if (l2>0 && v[P][l2]==v[P][l2-1]) continue;
J=v[P][l2];
if (J<50){
if (P-J>=0){
if (d[P][K]+1<d[P-J][J]){
d[P-J][J]=d[P][K]+1; pq.push(mp(-d[P][K]-1, mp(P-J, J)));
}
}
if (P+J<n){
if (d[P][K]+1<d[P+J][J]){
d[P+J][J]=d[P][K]+1; pq.push(mp(-d[P][K]-1, mp(P+J, J)));
}
}
}
else
for (int l=P%J; l<n; l+=J){
t=max((l-P)/J, -(l-P)/J)+d[P][K];
if (t<d[l][0]){
d[l][0]=t; pq.push(mp(-t, mp(l, 0)));
}
}
}
/*for (int l=0; l<m; ++l){
if ((p[l]-p[P])%j[P]) continue;
t=max((p[l]-p[P])/j[P], -(p[l]-p[P])/j[P])+d[P];
if (t<d[l]){
d[l]=t; pq.push(mp(-t, l));
}
}*/
}
cout << -1;
return 0;
}
