#include<bits/stdc++.h>
using namespace std;
const int maxn=30000+10;
int n,m,vis[maxn],dis[maxn],av;
unordered_set<int>fst[maxn];
vector<int>st[maxn];
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){
fst[i].insert(p);
}
for(int i=ind+p;i<n;i+=p){
fst[i].insert(p);
}
}
void solve(){
vector<pair<int,pair<int,int>>>di;
for(auto x:st[av]){
di.push_back(make_pair(0,make_pair(av,x)));
}
while((int)di.size()!=0){
vector<pair<int,pair<int,int>>>fake;
for(auto x:di){
if(x.second.first<0||x.second.first>=n){
continue;
}
if(fst[x.second.first].count(x.second.second)==0){
continue;
}
if(vis[x.second.first]==0){
vis[x.second.first]=1;
dis[x.second.first]=x.first;
}
fake.push_back(make_pair(x.first+1,make_pair(x.second.first-x.second.second,x.second.second)));
fake.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]){
fake.push_back(make_pair(x.first+1,make_pair(x.second.first-y,y)));
fake.push_back(make_pair(x.first+1,make_pair(x.second.first+y,y)));
}
st[x.second.first].clear();
}
swap(di,fake);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
int s=0;
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;
}
}
solve();
if(vis[s]){
cout<<dis[s]<<"\n";
}
else{
cout<<-1<<"\n";
}
}
