#include<bits/stdc++.h>
#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=3e4+10;
const ll mod=1e9+7;
const ll inf=1e9+500;
const ll rad=110;
const ll maxm=maxn*(rad)*3+50;
ll b[maxn];
ll p[maxn];
vector<ll> vec[maxn];
ll cn;
vector<pair<ll,bool> > ger[maxm];
bitset<maxm> h;
int main(){
ll n,m;
cin>>n>>m;
for(ll i=0;i<m;i++){
cin>>b[i]>>p[i];
vec[b[i]].pb(i);
}
for(ll i=0;i<n;i++){
for(auto v:vec[i]){
ger[i+m].pb(mp(v,0));
}
}
for(ll j=1;j<rad;j++){
for(ll i=0;i<n;i++){
ger[m+j*n+i].pb(mp(i+m,0));
if(i>=j){
ger[m+j*n+i].pb(mp(m+j*n+i-j,1));
}
}
}
for(ll j=1;j<rad;j++){
for(ll i=0;i<n;i++){
ll v=m+rad*n+(j-1)*n+i;
ger[v].pb(mp(i+m,0));
if(i+j<n){
ger[v].pb(mp(v+j,1));
}
}
}
for(ll i=0;i<m;i++){
if(p[i]<rad){
ll v=b[i];
ger[i].pb(mp(m+n*p[i]+v,0));
ger[i].pb(mp(m+rad*n+(p[i]-1)*n+v,0));
}
}
cn=m+n*2*rad+1;
for(ll i=0;i<m;i++){
if(p[i]>=rad){
ll mo=cn;
ger[i].pb(mp(cn,0));
ger[cn].pb(mp(b[i]+m,0));
cn++;
for(ll j=b[i]+p[i];j<n;j+=p[i]){
ger[cn].pb(mp(j+m,0));
ger[cn-1].pb(mp(cn,1));
cn++;
}
for(ll j=b[i]-p[i];j>=0;j-=p[i]){
ger[cn].pb(mp(j+m,0));
ger[mo].pb(mp(cn,1));
mo=cn;
cn++;
}
}
}
deque<pii>dk;
dk.pb(mp(0,1));
while(dk.size()){
ll v=dk.front().F;
ll w=dk.front().S;
dk.pop_front();
if(!h[v]){
if(v==1){
cout<<w-1;
return 0;
}
h[v]=1;
for(auto e:ger[v]){
if(e.S){
dk.push_back(mp(e.F,w+1));
}else{
dk.push_front(mp(e.F,w));
}
}
}
}
cout<<-1;
}
