#include<bits/stdc++.h> using namespace std; #define ll long long #define co cout<< // stuff void solve(){ ll n,k; cin>>n>>k; vector<ll>v[n+5]; ll dp[n+5]={}; for(int i=1;i<n;i++) dp[i]=1e18; for(int i=0;i<k;i++){ ll x,y; cin>>x>>y; v[x].push_back(y); } ll sqr=60; set<pair<ll,ll>>curr; curr.insert({0,0}); while(curr.size()){ auto [dis,i]=*curr.begin(); curr.erase(curr.begin()); 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}); } } } } co ((dp[1]==1e18)?-1:dp[1]); } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int _=1; // cin>>_; while(_--) solve(); }