Submission #67723114

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repp(i,l,r) for(ll i=l;i<r;i++)
#define ALL(V) V.begin(),V.end()
const ll INF=INT64_MAX/7;
const ll MOD=998244353;
using pll = pair<ll,ll>;
template<class T> bool chmax(T &a, T b) {if (a < b) {a = b; return true;} return false;}
template<class T> bool chmin(T &a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> using prique=priority_queue<T,vector<T>,greater<T>>;
#define PRINTRETURN(x) {cout<<x<<endl;return;}
#define PRINTRETURN0(x) {cout<<x<<endl;return 0;}

int main(){
    ll N,M;
    cin>>N>>M;
    // 行動が取れるなら最終状態の本数が多い方が絶対良い
    ll a,b,c;
    vector<tuple<ll,ll,ll>> V(M);
    prique<tuple<ll,ll,ll>> Q;
    rep(i,M){
        cin>>a>>b;
        Q.push({a-b,a,b});
    }
    ll ans=0;
    while(!Q.empty()){
        tie(c,a,b)=Q.top();
        Q.pop();
        if(N<a)continue;
        ll k=(N-a)/c+1;
        N-=c*k;
        ans+=k;
    }
    cout<<ans<<endl;
}

Submission Info

Judge Result