#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> pii;
#define f first
#define s second
#define nl '\n'
const int N=30001;
const int B=175;
int n,m;
vector<int> v[N];
int P[N], x[N];
int dist[N][B];
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i=0; i<m; i++){
cin >> x[i] >> P[i];
v[x[i]].push_back(i);
}
for(int i=0; i<n; i++){
for(int j=0; j<B; j++) dist[i][j]=1e9;
}
dist[0][0]=0;
set<pair<int, pii>> s;
s.insert({0, {0, 0}});
auto go=[&](int i, int d, int b){
// cout << "go " << i << " " << d << " " << b << nl;
for(int c:{i+b, i-b}){
if(c<0 || c>=n) continue;
// cout << "-> " << c << " " << b << nl;
if(d+1<dist[c][b]){
if(dist[c][b]!=1e9) s.erase({dist[c][b], {c, b}});
dist[c][b]=d+1;
s.insert({d+1, {c, b}});
}
if(d+1<dist[c][0]){
if(dist[c][0]!=1e9) s.erase({dist[c][0], {c, 0}});
dist[c][0]=d+1;
s.insert({d+1, {c, 0}});
}
}
};
while(!s.empty()){
auto p=*s.begin(); s.erase(s.begin());
int d=p.f, a=p.s.f, b=p.s.s;
// cout << a << " " << b << nl;
if(a==x[1]){
cout << d; return 0;
}
if(!b){
for(int i:v[a]){
if(P[i]>=B){
for(int j=a%P[i]; j<n; j+=P[i]){
if(d+abs(j-a)/P[i]<dist[j][0]){
if(dist[j][0]!=1e9) s.erase({dist[j][0], {j, 0}});
dist[j][0]=d+abs(j-a)/P[i];
s.insert({dist[j][0], {j, 0}});
}
}
}
else{
go(a, d, P[i]);
}
}
}
else{
go(a, d, b);
}
}
cout << -1;
}
