//Sorry but iam targeting IOI :))
//NEVER LOSE HOPE
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define endl "\n"
#define ceil(a,b) (a+(b-1))/b
#define all(v) v.begin(),v.end()
#define Hidden ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int N=3e4+10,mod = 1e9+7;
int n,m,f[N],dis[N];
pair<int,int>a[N];
vector<pair<int,int>>adj[N];
set<pair<int,int>>vis;
int main(){
cin>>n>>m;
for(int i=0;i<m;++i){
cin>>a[i].first>>a[i].second;
vis.insert({a[i].first,a[i].second});
}
for(auto i:vis){
for(int j=i.first+i.second;j<n;j+=i.second){
adj[i.first].push_back({j,((j-i.first)/i.second)});
if(vis.find({j,i.second})!=vis.end()) break;
}
}
for(auto i:vis){
for(int j=i.first-i.second;j>=0;j-=i.second){
adj[i.first].push_back({j,((i.first-j)/i.second)});
if(vis.find({j,i.second})!=vis.end()) break;
}
}
priority_queue<pair<int,int>>pq;
pq.push({0,a[0].first});
for(int i=0;i<N;++i) dis[i]=INT_MAX;
dis[a[0].first]=0;
while(!pq.empty()){
pair<int,int>p=pq.top();
pq.pop();
int u=p.second;
for(auto i:adj[u]){
int cost=dis[u]+i.second;
if(cost<dis[i.first]){
dis[i.first]=cost;
pq.push({-cost,i.first});
}
}
}
if(dis[a[1].first]==INT_MAX) cout<<"-1\n";
else cout<<dis[a[1].first]<<'\n';
}
