#include <cstdio> #include <queue> #include <algorithm> #include <cstring> using namespace std; typedef pair<int,int> pp; int N,M; int a[30010],P[30010]; int dist[30010]; bool chk[30010]; priority_queue<pp,vector<pp>,greater<pp> > Q; int main(){ scanf("%d%d",&N,&M); for(int i=0;i<M;i++){ scanf("%d%d",&a[i],&P[i]); } memset(dist,0x3f,sizeof(dist)); int INF=dist[0]; dist[0]=0; Q.push(pp(0,0)); int v; while(!Q.empty()){ do{ v=Q.top().second;Q.pop(); }while(!Q.empty()&&chk[v]); chk[v]=1; if(v==1)break; for(int i=0;i<M;i++){ if(abs(a[v]-a[i])%P[v]==0){ if(dist[i]>dist[v]+abs(a[v]-a[i])/P[v]){ dist[i]=dist[v]+abs(a[v]-a[i])/P[v]; Q.push(pp(dist[i],i)); } } } } if(dist[1]==INF){ puts("-1"); }else{ printf("%d",dist[1]); } }