#include <bits/stdc++.h>
using namespace std;
int n, m; const int SQ=10;
vector <int> pos [30010];
pair <int, int> l [30010];
int sol [30010][SQ+10];
int bio [30010][SQ+10];
typedef pair < int, pair <int, int> > byk;
priority_queue < byk, vector <byk>, greater <byk> > s;
int main(){
ios_base::sync_with_stdio (false);
cin.tie (0);
cin >> n >> m;
for (int i=0; i<m; i++) cin >> l [i].first >> l [i].second;
for (int i=0; i<m; i++) pos [l [i].first].push_back (l [i].second);
for (int i=0; i<n; i++){
for (int j=0; j<SQ+1; j++){
sol [i][j]=1e9;
s.push ({1e9, {i, j}});
}
}
s.push ({0, {l [0].first, l [0].second}});
sol [l [0].first][l [0].second]=0;
while (!s.empty ()){
byk tp = s.top();
int res=tp.first;
if (res==1e9) break;
int x=tp.second.first;
int p=tp.second.second;
s.pop();
//cout << res << " " << x << " " << p << endl;
bio [x][p]=1;
//cout << res << " " << x << " " << p << endl;
int siz = pos[x].size();
for (int i=0; i<siz; i++){
int po=pos [x][i];
if (po>SQ){
for (int j=x+po; j<n; j+=po){
if (sol [j][0]<=(j-x)/po+res || bio [j][0]) continue;
s.push ({sol [j][0]=(j-x)/po+res, {j, 0}});
}
for (int j=x-po; j>=0; j-=po){
if (sol [j][0]<=(x-j)/po+res || bio [j][0]) continue;
s.push ({sol [j][0]=(x-j)/po+res, {j, 0}});
}
}
else {
if (x-po>=0){
if (sol [x-po][po]>1+res && !bio [x-po][po]) {
sol [x-po][po]=1+res;
s.push ({sol [x-po][po], {x-po, po}});
}
}
if (x+po<n){
if (sol [x+po][po]>1+res && !bio [x+po][po]) {
sol [x+po][po]=1+res;
s.push ({sol [x+po][po], {x+po, po}});
}
}
}
}
if (x-p>=0 && p!=0){
if (sol [x-p][p]>1+res && !bio [x-p][p]) {
sol [x-p][p]=1+res;
s.push ({sol [x-p][p], {x-p, p}});
}
}
if (x+p<n && p!=0){
if (sol [x+p][p]>1+res && !bio [x+p][p]) {
sol [x+p][p]=1+res;
s.push ({sol [x+p][p], {x+p, p}});
}
}
}
int so=1e9;
for (int i=0; i<SQ+1; i++) so=min (so, sol [l [1].first][i]);
if (so==1e9) cout << -1;
else cout << so;
}
