#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,e,f,g,ans;
bool c,d,vs[30001];
vector<pair<int,int>> v[30001];
queue<tuple<int,int,bool,bool,int>> q;
int main(){
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>a>>b;
v[a].emplace_back(make_pair(b,i));
if(i==0){
e=a;
f=b;
}
else if(i==1){
ans=a;
}
}
q.emplace(make_tuple(e,0,0,0,0));
while(!q.empty()){
a=get<0>(q.front());
b=get<1>(q.front());
c=get<2>(q.front());
d=get<3>(q.front());
g=get<4>(q.front());
q.pop();
if(a==ans){
cout<<g;
return 0;
}
if(c==1&&a-b>=0){
q.emplace(make_tuple(a-b,b,1,0,g+1));
}
if(d==1&&a+b<n){
q.emplace(make_tuple(a+b,b,0,1,g+1));
}
for(int i=0;i<v[a].size();i++){
if(vs[v[a][i].second]==0){
vs[v[a][i].second]=1;
if(a-v[a][i].first>=0){
q.emplace(make_tuple(a-v[a][i].first,v[a][i].first,1,0,g+1));
}
if(a+v[a][i].first<n){
q.emplace(make_tuple(a+v[a][i].first,v[a][i].first,0,1,g+1));
}
}
}
}
cout<<"-1";
}
