#include<bits/stdc++.h>
using namespace std;
const int maxn=30000+10;
int n,m,av;
set<int>fst[maxn];
vector<int>st[maxn];
int s=0,te=0;
void upd(int ind,int p){
st[ind].push_back(p);
if(fst[ind].count(p)!=0){
return ;
}
fst[ind].insert(p);
for(int i=ind-p;i>=0;i-=p){
te++;
fst[i].insert(p);
}
for(int i=ind+p;i<n;i+=p){
te++;
fst[i].insert(p);
}
}
int solve(){
vector<pair<int,pair<int,int>>>di;
for(auto x:st[av]){
di.push_back(make_pair(0,make_pair(av,x)));
}
for(int i=0;i<(int)di.size();i++){
auto x=di[i];
if(x.second.first<0||x.second.first>=n){
continue;
}
if(fst[x.second.first].count(x.second.second)==0){
continue;
}
if(x.second.first==s){
return x.first;
}
di.push_back(make_pair(x.first+1,make_pair(x.second.first-x.second.second,x.second.second)));
di.push_back(make_pair(x.first+1,make_pair(x.second.first+x.second.second,x.second.second)));
fst[x.second.first].erase(x.second.second);
for(auto y:st[x.second.first]){
di.push_back(make_pair(x.first+1,make_pair(x.second.first-y,y)));
di.push_back(make_pair(x.first+1,make_pair(x.second.first+y,y)));
fst[x.second.first].erase(y);
}
st[x.second.first].clear();
}
return -1;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
upd(u,v);
if(i==1){
s=u;
}
if(i==0){
av=u;
}
}
if(te>3000000){
assert(0);
}
cout<<solve()<<"\n";
}
