#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int K = 50;
const int MAXN = 30000;
vector <pair <int, int>> graf[K*MAXN+5];
int dist[K*MAXN+5];
const int INF = 1000000000;
int gde[MAXN+5];
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int n, m;
cin >> n >> m;
for(int d=1; d<K; d++){
for(int i=0; i<n; i++) graf[K*i+d].push_back({K*i, 0});
for(int i=0; i+d<n; i++) graf[K*i+d].push_back({K*(i+d) + d, 1});
for(int i=n-1; i-d>=0; i--) graf[K*i+d].push_back({K*(i-d) + d, 1});
}
for(int j=0; j<m; j++){
int x, d;
cin >> x >> d;
gde[j] = K*x;
if(d < K) graf[K*x].push_back({K*x+d, 0});
else{
for(int i=x+d; i<n; i+=d) graf[K*x].push_back({K*i, (i-x)/d});
for(int i=x-d; i>=0; i-=d) graf[K*x].push_back({K*i, (x-i)/d});
}
}
for(int i=0; i<n*K; i++) dist[i] = INF;
dist[gde[0]] = 0;
set <pair <int, int>> q;
q.insert({0, gde[0]});
while(!q.empty()){
int v = q.begin()->second;
q.erase(q.begin());
for(auto pr : graf[v]){
int c = pr.first, d = pr.second;
if(dist[c] > dist[v] + d){
q.erase({dist[c], c});
dist[c] = dist[v] + d;
q.insert({dist[c], c});
}
}
}
if(dist[gde[1]] == INF) cout << "-1\n";
else cout << dist[gde[1]] << "\n";
return 0;
}
