// #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 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 endl "\n" #define pii pair<int,int> #define fi first #define se second #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; vector<vector<int>>pow(n); int s=sqrt(n); vector<vector<int>>dis(n,vector<int>(s+1,mod)); vector<int>di(n,mod); 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].append(p); } priority_queue<vector<int>,vector<vector<int>>,greater<>>q; q.push({0,st,mod}); di[st]=0; while(q.size()){ int u=q.top()[1],d=q.top()[0],ad=q.top()[2]; q.pop(); if(ad<=s){ if(d==dis[u][ad]) pow[u].append(ad); else continue; } else if(d>di[u]) continue; for(auto po:pow[u]){ if(po<=s){ dis[u][po]=min(dis[u][po],d); 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; } } } } pow[u].clear(); } if(di[en]>1e9) 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(); }