#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)3e4 + 4;
int N, M;
int B[NS], P[NS];
int far[NS], chk[NS];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<int> put[NS];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
for(int i = 0; i < M; ++i){
cin >> B[i] >> P[i];
put[B[i]].push_back(P[i]);
}
for(int i = 0; i < N; ++i){
sort(put[i].begin(), put[i].end());
put[i].erase(unique(put[i].begin(), put[i].end()), put[i].end());
far[i] = MOD;
}
far[B[0]] = 0;
pq.push({0, B[0]});
while(!pq.empty()){
while(!pq.empty() && chk[pq.top().second]){
pq.pop();
}
if(pq.empty()){
break;
}
int now = pq.top().second; pq.pop();
chk[now] = 1;
for(auto&jump:put[now]){
for(int mov = 1; now + mov * jump < N; ++mov){
int nxt = now + mov * jump;
if(far[now] + mov < far[nxt]){
far[nxt] = far[now] + mov;
pq.push({far[nxt], nxt});
}
int pos = lower_bound(put[nxt].begin(), put[nxt].end(), jump) - put[nxt].begin();
if(pos < (int)put[nxt].size() && put[nxt][pos] == jump){
break;
}
}
}
for(auto&jump:put[now]){
for(int mov = 1; now - mov * jump >= 0; ++mov){
int nxt = now - mov * jump;
if(far[now] + mov < far[nxt]){
far[nxt] = far[now] + mov;
pq.push({far[nxt], nxt});
}
int pos = lower_bound(put[nxt].begin(), put[nxt].end(), jump) - put[nxt].begin();
if(pos < (int)put[nxt].size() && put[nxt][pos] == jump){
break;
}
}
}
}
if(far[B[1]] == MOD){
cout << -1;
}
else{
cout << far[B[1]];
}
return 0;
}
