#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int N = 3e4, inf = 1e9;
const int bs = 300;
int n, m, dst[N][bs];
vector<int> dog[N];
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
int start = 0, finish = 0;
for(int i = 0;i < m;i++){
int x, y;
cin >> x >> y;
if(i == 0)
start = x;
else if(i == 1)
finish = x;
dog[x].push_back(y);
}
memset(dst, 0x3f, sizeof(dst));
priority_queue < pair< int, pair<int, int> > > st;
dst[start][0] = 0;
st.push(MP(0, MP(start, 0)));
while(!st.empty()){
pair< int, pair<int, int> > temp = st.top();
st.pop();
int dst_pos = -temp.X, pos = temp.Y.X, power = temp.Y.Y;
// cerr << dst_pos << " " << pos << "\n";
if(power == 0){
for(int it = 0;it < (int)dog[pos].size();it++){
power = dog[pos][it];
if(power < bs){
if(dst[pos][power] > dst_pos){
dst[pos][power] = dst_pos;
st.push(MP(-dst_pos, MP(pos, power)));
}
}
else{
for(int j = 1;pos - j * power >= 0;j++){
int next = pos - j * power;
if(dst[next][0] > dst_pos + j){
dst[next][0] = dst_pos + j;
st.push(MP(-dst[next][0], MP(next, 0)));
}
}
for(int j = 1;pos + j * power < n;j++){
int next = pos + j * power;
if(dst[next][0] > dst_pos + j){
dst[next][0] = dst_pos + j;
st.push(MP(-dst[next][0], MP(next, 0)));
}
}
}
}
}
else{
if(dst[pos][0] > dst_pos){
dst[pos][0] = dst_pos;
st.push(MP(-dst_pos, MP(pos, 0)));
}
if(pos - power >= 0 && dst[pos - power][power] > dst_pos + 1){
dst[pos - power][power] = dst_pos + 1;
st.push(MP(-dst_pos - 1, MP(pos - power, power)));
}
if(pos + power < n && dst[pos + power][power] > dst_pos + 1){
dst[pos + power][power] = dst_pos + 1;
st.push(MP(-dst_pos - 1, MP(pos + power, power)));
}
}
}
cout << (dst[finish][0] >= inf ? -1: dst[finish][0]);
}
