#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <ext/pb_ds/priority_queue.hpp>
#define MAXV 30010
#define MAXE 20000000
#define INF 999999999+208
using namespace std;
struct Pair
{
int first,second;
Pair(){}
Pair(int _f,int _s):first(_f),second(_s){}
};
inline bool operator>(Pair a,Pair b)
{
return a.first>b.first;
}
int read()
{
int ans=0;
char ch=getchar();
while(ch==' '||ch=='\n') ch=getchar();
while(ch>='0'&&ch<='9')
{
ans=ans*10+ch-'0';
ch=getchar();
}
return ans;
}
int n,m,K;
int dist[MAXV],poslist[MAXV],tot_diff=0;
bool vis[MAXV];
int S,T;
int b[MAXV];
vector<int>p[MAXV];
vector<int>::iterator it;
bool mark[MAXV];
typedef __gnu_pbds :: priority_queue<Pair,greater<Pair>,__gnu_pbds::thin_heap_tag > Heap;
//typedef __gnu_pbds::priority_queue <Pair,greater<Pair >,__gnu_pbds::thin_heap_tag> Heap;
Heap pq;
Heap::point_iterator posmark[MAXV];
inline void update(Pair pr)
{
if(dist[pr.second]>pr.first)
{
pq.modify(posmark[pr.second],pr);
dist[pr.second]=pr.first; //!!!!!!
}
}
int Heap_Dij()
{
memset(dist,127,sizeof(dist));
dist[S]=0;
for(int i=0;i<n;i++)
posmark[i]=pq.push(Pair(dist[i],i));
while(!pq.empty())
{
Pair now=pq.top();
pq.pop();
if(now.first>INF) return -1;
int i=now.second;
if(i==T) return now.first;
if(vis[i]) continue;
vis[i]=true;
for(int t=0;t<p[i].size();t++)
{
int P=p[i][t];
if(t>0&&P==p[i][t-1]) continue; //!!!!!
for(int j=i+P,k=1;j<n;j+=P,k++)
{
update(Pair(now.first+k,j));
it=lower_bound(p[j].begin(),p[j].end(),P);
if(it!=p[j].end()&&*it==P) break;
}
for(int j=i-P,k=1;j>=0;j-=P,k++)
{
update(Pair(now.first+k,j));
it=lower_bound(p[j].begin(),p[j].end(),P);
if(it!=p[j].end()&&*it==P) break;
}
}
}
return -1;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=m;i++)
{
int x;
b[i]=read();
x=read();
p[b[i]].push_back(x);
}
for(int i=0;i<n;i++)
sort(p[i].begin(),p[i].end());
S=b[1],T=b[2];
printf("%d\n",Heap_Dij());
return 0;
}
