#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
const int N=3e4;
const int inf=1e9+7;
const int LIM=N*174;
vector<int> lis[N<<1];
int b[N],p[N],dis[LIM],lst[N];
bool ok[N];
vector<pair<int,int> > adj[LIM];
//priority_queue<pair<int,int> > lis;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m,i,j,k,l=0;
cin>>n>>m;
for(i=0;i<m;i++){ //0->m-1
cin>>b[i]>>p[i];
if(ok[b[i]]){
adj[i].push_back({lst[b[i]],0});
}
l=max(l,p[i]);
lst[b[i]]=i;
ok[b[i]]=true;
}
int magic=sqrt(l)+1;
int lim=min(magic,n-1);
//m -> m+(n-1)*magic la cac nut dai dien cho cac luong van tai
for(i=1;i<=lim;++i){
for(j=0;j<n-i;++j){
k=(i-1)*n+j+m;
l=(i-1)*n+j+i+m;
adj[k].push_back({l,1});
adj[l].push_back({k,1});
}
}
for(i=0;i<m;++i){
if(i==lst[b[i]]){
for(j=1;j<=lim;++j){
k=(j-1)*n+b[i]+m;
adj[k].push_back({i,0});
}
}
if(p[i]>lim){
j=b[i];
k=0;
while(j>=0){
if(ok[j]){
adj[i].push_back({lst[j],k});
}
j-=p[i];
++k;
}
j=b[i];
k=0;
while(j+p[i]<n){
j+=p[i];
++k;
if(ok[j]){
adj[i].push_back({lst[j],k});
}
}
} //the dog, not the dai dien :'(
else{
k=(p[i]-1)*n+b[i]+m;
adj[i].push_back({k,0});
}
}
fill(dis+1,dis+LIM,inf);
// lis.push({0,0});
// while(lis.size()){
// j=-lis.top().first;
// k=lis.top().second;
// lis.pop();
// if(dis[k]==j){
// for(i=0;i<adj[k].size();++i){
// if(dis[adj[k][i].first]>dis[k]+adj[k][i].second){
// dis[adj[k][i].first]=dis[k]+adj[k][i].second;
// lis.push({-dis[adj[k][i].first],adj[k][i].first});
// }
// }
// }
// }
int cnt=1;
lis[dis[0]].push_back(0);
for(i=0;i<LIM&&cnt;++i){
while(lis[i].size()){
j=lis[i].back();
--cnt;
lis[i].pop_back();
if(dis[j]!=i){
continue;
}
for(k=0;k<adj[j].size();++k){
if(dis[adj[j][k].first]>dis[j]+adj[j][k].second){
dis[adj[j][k].first]=dis[j]+adj[j][k].second;
lis[dis[adj[j][k].first]].push_back(adj[j][k].first);
++cnt;
}
}
}
}
if(dis[1]!=inf){
cout<<dis[1];
}
else{
cout<<-1;
}
}
/*
5 3
0 2
1 1
4 1
*/
