#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair int n,m,s,e; vector<pair<int,int> > adj[30001]; set<int> pos[30001]; int dist[30001]; bool vis[30001]; stack<int> st; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>m; for (int i=0;i<m;i++){ int b,p; cin>>b>>p; if (i==0) s=b; if (i==1) e=b; pos[p].insert(b); } for (int i=1;i<30001;i++){ for (auto j:pos[i]){ vis[j]=true; st.push(j); } for (auto j:pos[i]){ int dis=1; for (int k=j+i;k<n;k+=i){ adj[j].pb(mp(k,dis)); dis++; if (vis[k]) break; } dis=1; for (int k=j-i;k>=0;k-=i){ adj[j].pb(mp(k,dis)); dis++; if (vis[k]) break; } } while (!st.empty()){ vis[st.top()]=false; st.pop(); } } for (int i=0;i<n;i++) dist[i]=1e9; priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq; pq.push(mp(0,s)); dist[s]=0; while (!pq.empty()){ pair<int,int> cur=pq.top(); pq.pop(); if (dist[cur.second]<cur.first) continue; for (auto i:adj[cur.second]){ if (dist[i.first]>cur.first+i.second){ dist[i.first]=cur.first+i.second; pq.push(mp(cur.first+i.second,i.first)); } } } if (dist[e]==1e9) cout<<-1; else cout<<dist[e]; }