#include "bits/stdc++.h"
#define ll long long int
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define sz size()
const int N = 3e4 + 5;
using namespace std;
int n, m, b[N], p[N];
vector <pii> v[N];
priority_queue <pii> pq;
vector <int> dis(N,1e9), q[N];
map <pii,int> mp;
void f(){
pq.push({0,b[1]});
dis[b[1]] = 0;
while(!pq.empty()){
int a = pq.top().ss;
pq.pop();
for(auto i: v[a]){
if(dis[a] + i.ss < dis[i.ff]){
dis[i.ff] = dis[a] + i.ss;
pq.push({-dis[i.ff],i.ff});
}
}
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
//freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
cin >> n >> m;
for(int i = 1; i <= m; i++){
cin >> b[i] >> p[i];
if(mp.find({b[i],p[i]}) == mp.end()){
mp[{b[i],p[i]}] = 1;
q[b[i]].pb(p[i]);
}
}
for(int i = 0; i < n; i++){
for(auto j: q[i]){
int nd = i, cnt = 0;
while(1){
nd -= j;
if(nd < 0) break;
cnt++;
v[i].pb({nd,cnt});
if(mp.find({nd,j}) != mp.end()) break;
}
nd = i, cnt = 0;
while(1){
nd += j;
if(nd > n-1) break;
cnt++;
v[i].pb({nd,cnt});
if(mp.find({nd,j}) != mp.end()) break;
}
}
}
f();
cout << (dis[b[2]] == 1e9 ? -1 : dis[b[2]]);
}
