// In The Name Of God
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int>pii;
typedef pair<ll,ll> pll;
#define pb push_back
#define endl '\n'
#define test(x) cout<<x,exit(0)
#define fast (ios_base::sync_with_stdio(false),cin.tie(NULL))
const int maxn=3e4+10;
const int inf=1e9+10;
vector<int>vec[maxn];
int dis[maxn];
int mark[maxn];
int n,m;
void upd(int v){
mark[v]=1;
for(int i=0;i<vec[v].size();i++){
int p=vec[v][i];
for(int j=v+p;j<n;j+=p){
dis[j]=min(dis[j],dis[v]+(j-v)/p);
}
for(int j=v-p;j>=0;j-=p){
dis[j]=min(dis[j],dis[v]+(v-j)/p);
}
}
}
int main(){
fast;
for(int i=0;i<maxn;i++){
dis[i]=inf;
}
cin>>n>>m;
int start;
int en;
for(int i=1;i<=m;i++){
int b,p;cin>>b>>p;
if(i==1){
start=b;
}
if(i==2){
en=b;
}
vec[b].pb(p);
}
dis[start]=0;
upd(start);
for(int i=0;i<n-1;i++){
int mn=inf+100;
int who;
for(int j=0;j<n;j++){
if(mark[j]==0 and dis[j]<mn){
mn=dis[j];
who=j;
}
}
upd(who);
}
if(dis[en]>1e7){
cout<<-1<<endl;
}
else{
cout<<dis[en]<<endl;
}
}
