#include<bits/stdc++.h>
using namespace std;
unordered_map<int, int> dis[30005];
vector<int> doge[30005];
int p[30005], l[30005];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m; cin>>n>>m;
for(int i = 0; i < m; i++){
cin>>p[i]>>l[i];
doge[p[i]].push_back(l[i]);
}
deque<pair<int, int>> w;
dis[p[0]][l[0]] = 1; w.push_back({p[0], l[0]});
while(w.size() > 0){
int r = w.front().first, c = w.front().second, d = dis[r][c];
//cerr<<"A"<<r<<" "<<c<<" "<<d<<endl;
w.pop_front();
//Go to another place
if(r-c >= 0){
if(dis[r-c][c] == 0){dis[r-c][c] = d+1; w.push_back({r-c, c});};
}
if(r+c < n){
if(dis[r+c][c] == 0){dis[r+c][c] = d+1; w.push_back({r+c, c});};
}
//Transition to other doges
for(int x : doge[r]){
if(dis[r][x] == 0){dis[r][x] = d; w.push_front({r, x});}
}
}
int ans = 1e9;
for(pair<int, int> i : dis[p[1]]) ans = min(ans, i.second-1);
if(ans > n) cout<<-1;
else cout<<ans;
}
