#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 main(){
int n, m;
cin>>n>>m;
for (int i=1;i<K;i++){
for (int j=1;j + i <= n;j++){
nei[i * N + j].push_back({i + i * N + j, 1});
nei[i * N + j + i].push_back({i * N + j, 1});
}
for (int j=1;j<=n;j++)
nei[i * N + j].push_back({j, 0});
}
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[2] == 1e9)
Min[2] = -1;
cout<<Min[2]<<endl;
}
