#include<bits/stdc++.h>
#define int long long
using namespace std;
map<pair<int,int>,vector<int>>mp;
vector<pair<int,int>>adj[1000005];
int dis[1000005];
int inf=1e15;
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,m;cin>>n>>m;
int st=0,en=0;
for(int i=0;i<m;i++){
int b,p;cin>>b>>p;
if(i==0)st=b;
if(i==1)en=b;
mp[{b%p,p}].push_back(b);
}
int id=n-1;
for(auto x:mp){
int cur=x.first.first;
int p=x.first.second;
for(auto b:x.second)adj[b].push_back({id+(b-cur)/p+1,0});
for(cur;cur<n;cur+=p){
id++;
adj[id].push_back({cur,0});
if(cur!=x.first.first)adj[id-1].push_back({id,1});
}
cur=x.first.first;
for(auto b:x.second)adj[b].push_back({id+(b-cur)/p+1,0});
for(cur;cur<n;cur+=p){
id++;
adj[id].push_back({cur,0});
if(cur!=x.first.first)adj[id].push_back({id-1,1});
}
}
for(int i=0;i<=id;i++)dis[i]=inf;
deque<pair<int,int>>dq;
dq.push_back({0,st});
while(!dq.empty()){
auto [d,u]=dq.front();
dq.pop_front();
if(d>=dis[u])continue;
dis[u]=d;
for(auto v:adj[u]){
if(v.second)dq.push_back({d+1,v.first});
else dq.push_front({d,v.first});
}
}
if(dis[en]==inf)cout<<-1;
else cout<<dis[en];
}
