#include<bits/stdc++.h>
#define I inline void
using ll = long long ;
using ld = long double ;
using namespace std ;
const int N = 1e5 + 7 , mod = 1e9+7 ;
// how interesting!
int n;
int d[N] ;
vector<pair<int , int > > adj[N] ;
bool skys[30001][30001] , ed[30001][30001];
int st , en ;
I dijkstra(){
priority_queue<pair<int , int> > qu ;
qu.push({0 , st}) ;
d[st] = 0 ;
while(qu.size()){
int dst = -qu.top().first ;
int node = qu.top().second ;
qu.pop() ;
for(auto u : adj[node]){
if(d[u.first] == -1 || dst + u.second < d[u.first]){
d[u.first] = dst + u.second ;
qu.push({-d[u.first] , u.first}) ;
}
}
}
}
set<int> sts[N] ;
int main(){
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
//freopen("in.in" , "r" , stdin) ;
memset(d , -1 , sizeof d) ;
int m;
cin >> n >> m;
for(int i = 0 ;i < m;i++){
int a , b;
cin >> a >> b;
if(i == 0)
st = a ;
if(i == 1 )
en = a;
sts[a].insert(b) ;
}
for(int i = 0 ;i < n;i++){
for(auto u : sts[i]){
for(int j = 1 ; i + u * j < n ;j ++){
int cur = i + u * j ;
adj[i].push_back({i + u * j , j }) ;
if(sts[cur].count(u))
break ;
}
for(int j = 1 ; i - u * j >=0 ;j ++){
int cur = i - u * j ;
adj[i].push_back({i - u * j , j }) ;
if(sts[cur].count(u))
break ;
}
}
}
dijkstra() ;
cout<< d[en] ;
return 0 ;
}
