#include<bits/stdc++.h>
using namespace std ;
const int maxn = 3e4+123 , INF=1e9+7 ;
priority_queue <pair<int,int> , vector <pair<int,int>> , greater<pair<int,int>> >dijks ;
vector <int> doge[maxn] ;
int n , m ;
int visited[maxn] ;
void dijk(int t){
while(!dijks.empty()){
auto [pay , ver] =dijks.top();
dijks.pop() ;
if(ver==t){
cout<<pay ;
return ;
}
if(visited[ver]==pay){
//cout<<ver<<' '<<pay<<' ' ;
for(int i:doge[ver]){
for(int cnt=1+pay , verp=ver+i ; verp<n ; cnt++ , verp+=i){
if(visited[verp] > cnt) {
dijks.push({cnt , verp}) ;
visited[verp]=cnt ;
}
}
for(int cnt=1+pay , verp=ver-i ; verp>=0 ; cnt++ , verp-=i){
if(visited[verp] > cnt) {
dijks.push({cnt , verp}) ;
visited[verp]=cnt ;
}
}
doge[ver].clear() ;
doge[ver].shrink_to_fit();
}
//cout<<bfs.size()<<'\n';
}
}
cout<<-1 ;
}
int main(){
cin>>n>>m ;
fill(visited , visited+n+1 , INF) ;
int loc , p;
cin>>loc>>p ;
doge[loc].push_back(p) ;
dijks.push({0,loc}) ;
visited[loc]=0 ;
cin>>loc>>p ;
for(int i=2 ; i<m ;i++){
int loco;
cin>>loco>>p ;
doge[loco].push_back(p) ;
}
dijk(loc) ;
}
