/*
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma,tune=native")
//*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int ,int > pii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn = 30100;
const ll mod =1e9+7;
const ld PI = acos((ld)-1);
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}
int n , m;
int b[maxn] , p[maxn];
int dist[500][maxn];
struct tr{
int d , p , pos;
tr(int a , int b , int x):
d(a) , p(b) , pos(x){}
friend bool operator < (tr a , tr b){
return(a.d > b.d);
}
};
vector < int > vec[maxn];
priority_queue < tr > q;
void add(int d , int p , int pos){
int cur = d;
int x = pos;
while(x - p > -1){
x-=p;
cur++;
if(dist[0][x] > cur){
dist[0][x] = cur;
q.push({cur , 0 , x});
}
}
cur = d;
x = pos;
while(x + p < n){
x += p;
cur++;
if(dist[0][x] > cur){
dist[0][x] = cur;
q.push({cur , 0 , x});
}
}
}
void djk(){
ms(dist , 63);
dist[0][b[0]] = 0;
q.push({ 0 , 0 , b[0]});
while(!q.empty()){
auto v = q.top();
q.pop();
if(v.p == 0){ //jasoosi
for(auto x : vec[v.pos]){
if(p[x] < 300 and dist[p[x]][v.pos] > v.d )
dist[p[x]][v.pos] = v.d,
q.push({v.d , p[x] , v.pos});
else{
add(v.d , p[x] , v.pos);
}
}
}
else{
if(dist[0][v.pos] > v.d){
dist[0][v.pos] = v.d;
q.push({v.d , 0 , v.pos});
}
if(v.pos + v.p < n and dist[v.p][v.pos + v.p] > v.d + 1){
dist[v.p][v.pos + v.p] = v.d + 1;
q.push({v.d + 1 , v.p , v.pos + v.p});
}
if(v.pos - v.p > -1 and dist[v.p][v.pos - v.p] > v.d + 1){
dist[v.p][v.pos - v.p] = v.d + 1;
q.push({v.d + 1 , v.p , v.pos - v.p});
}
}
}
if(dist[0][b[1]] == dist[400][2])
dokme(-1);
dokme(dist[0][b[1]]);
}
int32_t main(){
migmig;
cin >> n >> m;
for(int i = 0 ; i < m ; i ++)
cin >> b[i] >> p[i];
for(int i = 0 ; i < m ; i ++)
vec[b[i]].pb(i);
djk();
return(0);
}
