各生徒に貸し出す本は、難易度 \(T_j\) 以下かつ面白さが最大であるものであることを思い出してください。

すると、以下の解法が成り立ちます。

• 本を難易度の昇順にソートした列を \(S\) とする。
  • タイブレークは任意に行ってよい。
• 各生徒について、 \(S\) の先頭から難易度が \(T_j\) 以下である本のうち最も面白いものの面白さを求めることができればこの問題に正解できる。
• そこで、 \(S\) を先頭から見て、各本の面白さを「その本かそれ以前に \(S\) に現れた本のうち最も面白いものの面白さ」に書き換える。
  • この書き換えは「本 \(x\) の代わりにより難易度が低く、より面白い本 \(y\) を読ませる」という指示と同等なので、答えは変化しない。
• この書き換えを行うことで、各生徒に貸し出すべきはその生徒が読める最も難しい本となる。
  • タイブレークとして、 \(S\) 中でより後ろに出てくる本を採用する必要がある。
• これは配列上を二分探索することで求められる。

時間計算量は \(O((M+N) \log M)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
using pl=pair<ll,ll>;

int main(){
  ll N,M;
  cin >> N >> M;
  vector<pl> vp(M);
  for(auto &nx : vp){
    cin >> nx.second >> nx.first;
  }
  sort(vp.begin(),vp.end());

  ll best=0;
  for(auto &nx : vp){
    best=max(best,nx.second);
    nx.second=best;
  }

  ll res=0;
  while(N--){
    ll T;
    cin >> T;
    
    auto it=lower_bound(vp.begin(),vp.end(),pl{T+1,-1});
    if(it!=vp.begin()){
      it--;
      res+=(*it).second;
    }
  }
  cout << res << "\n";
  return 0;
}