#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define td(v) v.begin(),v.end()
#define sz(v) (int)v.size()
//#define int long long
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
#define left sefude
#define right sefudermano
typedef long long ll;
typedef pair<int,int> pii;
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll a,ll b,ll m){
if(b==0LL) return 1LL;
if(b==1LL) return mod(a,m);
ll k = mod(exp(a,b/2,m),m);
if(b&1LL){
return mod(a*mod(k*k,m),m);
}
else return mod(k*k,m);
}
int n,m;
const int N = 3e4 + 10;
int b[N],p[N];
const int sq = 200;
bool vis[N][sq + 2];
int dist[N][sq + 2];
vi aqui[N];
int mn[N];
const int inf = 1e9;
vector<pii> pq[N*sq];
#define pwr(x) (x>=sq ? sq + 1 : x)
void djkistra(){
for(int i=0;i<N;i++){
mn[i] = inf;
for(int j=0;j<sq+2;j++)dist[i][j] = inf;
}
dist[b[0]][pwr(p[0])] =0;
mn[b[0]] = 0;
pq[0].pb(pii(b[0],p[0]));
for(int D=0;!pq[D].empty();D++){
while(!pq[D].empty()){
pii c = pq[D].back();
pq[D].pop_back();
if(vis[c.ff][pwr(c.ss)])continue;
vis[c.ff][pwr(c.ss)]=1;
int d = dist[c.ff][pwr(c.ss)];
int id = c.ff;
int cur = c.ff;
if(mn[cur] > d)mn[cur] = d;
if(c.ss < sq){
aqui[id].pb(c.ss);
}
for(int x : aqui[id]){
if(x >= sq){
int t=0;
for(int l = cur-x;l>=0;l-=x){
t++;
if(mn[l] > d + t){
mn[l] = dist[l][sq+1] = d + t;
}
pq[mn[l]].pb(pii(l,x));
}
t=0;
for(int l = cur + x;l<n;l+=x){
t++;
if(mn[l] > d + t){
mn[l] = dist[l][sq + 1] = d + t;
}
pq[mn[l]].pb(pii(l,x));
}
}else{
dist[cur][x] = min(dist[cur][x],d);
if(cur - x >=0 and dist[cur-x][x] == inf){
dist[cur-x][x] = d + 1;
if(mn[cur-x] > d+1)mn[cur-x] = d+1;
if(!vis[cur-x][x])pq[d+1].pb(pii(cur - x,x));
}
if(cur + x < n and dist[cur + x][x] == inf){
dist[cur + x][x] = d + 1;
if(mn[cur+x] > d+1)mn[cur+x] = d+1;
if(!vis[cur+x][x])pq[d+1].pb(pii(cur + x,x));
}
}
}
aqui[id].clear();
}
}
int res = mn[b[1]];
if(res == inf)cout<<-1<<endl;
else cout << res << endl;
}
int32_t main(){
fastio;
cin >> n >> m;
for(int i=0;i<m;i++){
cin >> b[i] >> p[i];
aqui[b[i]].pb(p[i]);
}
djkistra();
// Math -> gcd it all
// Did u check N=1? Did you switch N,M?
}
