#include <bits/stdc++.h>
using namespace std;
int n, m;
struct bg{
int pos, jump;
} a[30005];
namespace sub1234{
vector <int> pos[30005];
#define data array <int, 3>
int dist[2005][2005];
void solve(){
for(int i = 1; i <= m; i++) pos[a[i].pos].push_back(i);
memset(dist, 0x3f, sizeof dist);
priority_queue <data, vector <data>, greater <data>> pq;
pq.push({dist[a[1].pos][a[1].jump] = 0, a[1].pos, a[1].jump});
while(!pq.empty()){
int u = pq.top()[1], jump = pq.top()[2], cost = pq.top()[0];
pq.pop();
if(cost > dist[u][jump]) continue;
if(u == a[2].pos) return void(cout << cost);
if(u - jump >= 1 && dist[u - jump][jump] > cost + 1){
dist[u - jump][jump] = cost + 1;
pq.push({cost + 1, u - jump, jump});
}
if(u + jump <= n && dist[u + jump][jump] > cost + 1){
dist[u + jump][jump] = cost + 1;
pq.push({cost + 1, u + jump, jump});
}
for(int &id : pos[u]){
if(dist[u][a[id].jump] > cost){
dist[u][a[id].jump] = cost;
pq.push({cost, u, a[id].jump});
}
}
}
cout << - 1;
}
}
namespace sub5{
int dp[30005];
vector <int> pos[30005];
void solve(){
memset(dp, 0x3f, sizeof dp);
for(int i = 1; i <= m; i++) pos[a[i].pos].push_back(a[i].jump);
for(int i = 1; i <= n; i++){
sort(pos[i].begin(), pos[i].end());
// pos[i].unique(pos[i].begin(), pos[i].end()) - pos[i].begin();
unique(pos[i].begin(), pos[i].end()) - pos[i].begin();
}
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> pq;
pq.push({dp[a[1].pos] = 0, a[1].pos});
while(!pq.empty()){
int u = pq.top().second, cost = pq.top().first;
pq.pop();
if(cost > dp[u]) continue;
if(u == a[2].pos) return void(cout << cost);
for(int &p : pos[u]){
for(int v = u + p, w = 1; v <= n; v+= p, w++){
if(dp[v] > cost + w){
dp[v] = cost + w;
pq.push({dp[v], v});
}
}
for(int v = u - p, w = 1; v >= 1; v-= p, w++){
if(dp[v] > cost + w){
dp[v] = cost + w;
pq.push({dp[v], v});
}
}
}
}
cout << - 1;
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#define taskname "kieuoanh"
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout);
}
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> a[i].pos >> a[i].jump;
a[i].pos++;
}
// if(n <= 2000 && m <= 30000) return sub1234::solve(), 0;
return sub5::solve(), 0;
return 0;
}
