#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[300][N];
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[0][start] = 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[power][pos] > dst_pos){
dst[power][pos] = 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[0][next] > dst_pos + j){
dst[0][next] = dst_pos + j;
st.push(MP(-dst[0][next], MP(next, 0)));
}
}
for(int j = 1;pos + j * power < n;j++){
int next = pos + j * power;
if(dst[0][next] > dst_pos + j){
dst[0][next] = dst_pos + j;
st.push(MP(-dst[0][next], MP(next, 0)));
}
}
}
}
}
else{
if(dst[0][pos] > dst_pos){
dst[0][pos] = dst_pos;
st.push(MP(-dst_pos, MP(pos, 0)));
}
if(pos - power >= 0 && dst[power][pos - power] > dst_pos + 1){
dst[power][pos - power] = dst_pos + 1;
st.push(MP(-dst_pos - 1, MP(pos - power, power)));
}
if(pos + power < n && dst[power][pos + power] > dst_pos + 1){
dst[power][pos + power] = dst_pos + 1;
st.push(MP(-dst_pos - 1, MP(pos + power, power)));
}
}
}
cout << (dst[0][finish] >= inf ? -1: dst[0][finish]);
}
