#include<bits/stdc++.h> using namespace std; #define ll long long #define co cout<< // stuff void solve(){ ll n,m; cin>>n>>m; vector<ll>v[n+5],to[60][60]; ll dp[n+5]={}; for(int i=0;i<n;i++) dp[i]=1e18; ll st=-1,en=-1; for(int i=0;i<m;i++){ ll x,y; cin>>x>>y; for(int j=1;j<60;j++) to[j][x%j].push_back(x); if(st==-1) st=x; else if(en==-1) en=x; v[x].push_back(y); } set<pair<ll,ll>>curr; curr.insert({0,st}); dp[st]=0; while(curr.size()){ auto [dis,i]=*curr.begin(); curr.erase(curr.begin()); for(auto j:v[i]){ if(j>=60){ for(auto j:v[i]){ for(int k=1;i+j*k<n;k++){ ll x=i+j*k; if(dp[x]>dp[i]+k){ curr.erase({dp[x],x}); dp[x]=dp[i]+k; curr.insert({dp[x],x}); } } for(int k=1;i-j*k>=0;k++){ ll x=i-j*k; if(dp[x]>dp[i]+k){ curr.erase({dp[x],x}); dp[x]=dp[i]+k; curr.insert({dp[x],x}); } } } } else{ for(auto j:v[i]){ for(auto k:to[j][i%j]){ ll dist=abs(i-k)/j; if(dp[i]+dist<dp[k]){ curr.erase({dp[k],k}); dp[k]=dp[i]+dist; curr.insert({dp[k],k}); } } to[j][i%j].clear(); } } } } co ((dp[en]==1e18)?-1:dp[en]); } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int _=1; // cin>>_; while(_--) solve(); }