#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int N = 30005, K = 180;
vector<pair<int,int>> nei[N * K];
int Min[N * K], a[N], p[N];
void dijkstra(){
for (int i=1;i<N * K;i++)
Min[i] = 1e9;
Min[a[1]] = 0;
set<pair<int,int>> st = {{0, a[1]}};
while (st.size() > 0){
auto [mn, u] = *st.begin();
st.erase(begin(st));
for (auto [i, w] : nei[u]){
if (Min[i] > Min[u] + w){
st.erase({Min[i], i});
Min[i] = Min[u] + w;
st.insert({Min[i], i});
}
}
int i = u % N;
if (Min[i] > Min[u]){
st.erase({Min[i], i});
Min[i] = Min[u];
st.insert({Min[i], i});
}
i = u - u / N;
if (u / N == i / N and Min[i] > Min[u] + 1){
st.erase({Min[i], i});
Min[i] = Min[u] + 1;
st.insert({Min[i], i});
}
i = u + u / N;
if (u / N == i / N and Min[i] > Min[u] + 1){
st.erase({Min[i], i});
Min[i] = Min[u] + 1;
st.insert({Min[i], i});
}
}
}
int main(){
int n, m;
cin>>n>>m;
for (int i=1;i<=m;i++){
cin>>a[i]>>p[i];
a[i]++;
if (p[i] >= K){
for (int j=a[i] - p[i] * (a[i] / p[i]);j <= n;j += p[i])
if (j != a[i])
nei[a[i]].push_back({j, abs(a[i] - j) / p[i]});
}
else
nei[a[i]].push_back({p[i] * N + a[i], 0});
}
dijkstra();
if (Min[a[2]] == 1e9)
Min[a[2]] = -1;
cout<<Min[a[2]]<<endl;
}
