#ifdef __AVX2__ #pragma GCC target "avx2" #endif #pragma GCC optimize "O3" #pragma GCC optimize "unroll-loops" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #define int long long #define elif else if #define all(l) begin(l),end(l) #define rall(l) rbegin(l),rend(l) #define append push_back #define print(l) for(auto i:l) cout<<i<<' '; cout<<endl; #define pprint(a,b) cout<<a<<' '<<b<<endl; #define inp(l) for(auto &i:l) cin>>i; #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> #define pai make_pair #define endl "\n" #define pii pair<int,int> #define fi first #define se second #define vec vector #define ins(a,b,c) a.insert(begin(a)+b,c); // const int mod=998244353; const int mod1=998244353; const int mod=1e9+7; const int N=2e5+5; int iter=1,itera=1; void solve(){ int n,m; cin>>n>>m; vec<set<int>>pow(n); int s=sqrt(n); vec<vec<int>>dis(n,vec<int>(s+1,1e18)); vec<int>di(n+1,1e18); int st,en; for(int i=0;i<m;i++){ int b,p; cin>>b>>p; if(i==0) st=b; if(i==1) en=b; pow[b].insert(p); } priority_queue<vec<int>,vec<vec<int>>,greater<>>q; q.push({0,st,mod}); while(q.size()){ int u=q.top()[1],d=q.top()[0],ad=q.top()[2]; q.pop(); bool f=1; if(!f) continue; if(ad<=s){ if(d==dis[u][ad]) pow[u].insert(ad); else f=0; } else if(d>di[u]) f=0; if(!f) continue; for(auto po:pow[u]){ if(po<=s){ if(u>=po){ if(d+1<dis[u-po][po]){ di[u-po]=min(d+1,di[u-po]); dis[u-po][po]=d+1; q.push({d+1,u-po,po}); } } if(u+po<n){ if(d+1<dis[u+po][po]){ di[u+po]=min(d+1,di[u+po]); dis[u+po][po]=d+1; q.push({d+1,u+po,po}); } } } else{ int tem=d; for(int i=u-po;i>=0;i-=po){ tem++; if(tem<di[i]){ q.push({tem,i,po}); di[i]=tem; } } tem=d; for(int i=u+po;i<n;i+=po){ tem++; if(tem<di[i]){ q.push({tem,i,po}); di[i]=tem; } } } } } if(di[en]>1e15) cout<<"-1\n"; else cout<<di[en]<<endl; } signed main(){ // freopen("","r",stdin); // freopen("","w",stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout<<fixed<<setprecision(20); // cin>>itera; for(iter=1;iter<=itera;iter++) solve(); }