#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] ;
set<pair<int , int > > adj[N] ;
bool skys[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}) ;
}
}
}
}
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;
if(skys[a][n+b] || skys[a][n-b])
continue ;
//skys[a][b] = skys[a][-b] = 1 ;
int cur = a + b , j = 0 ;
while(cur < n ){
adj[a].insert({cur , ++j}) ;
cur+= b;
if(skys[cur][n+b])break ;
}
cur = a - b , j = 0 ;
while(cur >= 0){
adj[a].insert({cur , ++j}) ;
cur-=b ;
if(cur >= 0 && skys[cur][n+b])
break ;
}
}
dijkstra() ;
cout<< d[en] ;
return 0 ;
}
