#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=2010;
const ll mod=1e9+7;
const ll inf=1e9+500;
const ll rad=2010;
const ll maxm=maxn*(rad)*2+50;
ll b[maxn];
ll p[maxn];
vector<ll> vec[maxn];
vector<pair<ll,short> > ger[maxm];
ll h[maxm];
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));
}
}
for(ll i=0;i<m;i++){
if(p[i]>=rad){
for(ll j=b[i]+p[i];j<n;j+=p[i]){
ger[i].pb(mp(j+m,(j-b[i])/p[i]));
}
for(ll j=b[i]-p[i];j>=0;j-=p[i]){
ger[i].pb(mp(j+m,(b[i]-j)/p[i]));
}
}
}
deque<pii> dk;
dk.pb(mp(1,0));
while(dk.size()){
ll v=dk.front().S;
ll w=dk.front().F;
dk.pop_front();
if(h[v]==0){
h[v]=w;
for(auto e:ger[v]){
if(e.S){
dk.pb(mp(w+1,e.F));
}else{
dk.push_front(mp(w,e.F));
}
}
}
}
/*
set<pii> st;
set<pii> :: iterator it;
st.insert(mp(1,0));
while(st.size()){
it=st.begin();
ll v=(*it).S;
ll w=(*it).F;
st.erase(it);
if(h[v]==0){
h[v]=w;
for(auto e:ger[v]){
st.insert(mp(e.S+w,e.F));
}
}
}*/
if(h[1]==0){
cout<<-1;
}else{
cout<<h[1]-1;
}
}
/*
. _______ __ ___ ________ ________ _________ _________ ________
. / \ | | / / / \ | \ / \ | | | __ \
. / _____/ | | / / / ___ \ | ___ \ | _______/ | ______| | | \ \
. / / | |/ / / / \ \ | | \ \ | (______ | |_____ | |__/ /
. | | | / | / \ | | | | | \ \ | | | __/
. | | | \ | \ / | | | | | \______ \ | ______| | \
. \ \_____ | |\ \ \ \___/ / | |___/ / _______) | | |_____ | |\ \
. \ \ | | \ \ \ / | / / / | | | | \ \
Compilation message
skyscraper.cpp:122:97: warning: backslash-newline at end of file
. | | | \ | \ / | | | | | \______ \ | ______| | \
skyscraper.cpp:116:1: error: unterminated comment
/*
^
