#include <bits/stdc++.h>
#define int long long
int b[30010];
int p[30010];
int dist[30010];
std::vector<int> v[30010];
signed main() {
int n,m;
std::cin >> n >> m;
int s=0,e=1;
for(int i=0;i<m;i++){
std::cin >> b[i] >> p[i];
if(i==0)s=b[i];
else if(i==1)e=b[i];
v[b[i]].push_back(p[i]);
}
for(int i=0;i<n;i++){
std::sort(v[i].begin(),v[i].end());
v[i].erase(std::unique(v[i].begin(),v[i].end()),v[i].end());
dist[i]=1e18;
}
std::priority_queue<std::pair<int,int>> pq;
dist[s]=0;
pq.push({-0,s});
while(!pq.empty()){
int weight=-pq.top().first;
int node=pq.top().second;
if(weight > dist[node]) continue;
pq.pop();
for(auto p:v[node]){
for(int j=node+p;j<n;j+=p){
int w=(j-node)/p;
if(weight+w<dist[j]){
dist[j]=weight+w;
pq.push({-(dist[j]),j});
}
}
for(int j=node-p;j>=0;j-=p){
int w=(node-j)/p;
if(weight+w<dist[j]){
dist[j]=weight+w;
pq.push({-(dist[j]),j});
}
}
}
}
if(dist[e]>=1e18)dist[e]=-1;
std::cout << dist[e];
}
