イベントソート と imos法 との考えを組み合わせることでこの問題に正解できます。

宝箱を以下のイベントに言い換えます。

• 座標 \(X_i\) に価値 \(C_i\) の宝箱を設置する。

また、魔法を以下のイベントに言い換えます。

• 座標 \(L_i\) に、「解錠の開始」を \(1\) つ設置する。
• 座標 \(R_i+1\) に、「解錠の終了」を \(1\) つ設置する。
• 同一座標上のイベントでは、解錠関連のものを宝箱のものより前に処理するよう取り決める。 … ★

上記の \(3\) 種のイベントを座標の昇順に並べ替え、その順に処理することを考えます。

• 今着目している座標の解錠が行われている魔法の数 \(h=0\) を用意する。
• イベントを座標の昇順に処理する。ただし、 ★ の取り決めを遵守できるように並べる。
  • 「解錠の開始」が現れた場合、 \(h\) に \(1\) 加算する。
  • 「解錠の終了」が現れた場合、 \(h\) から \(1\) 減算する。
  • 宝箱が現れた場合、 \(h>0\) である、またその時に限り、その宝箱を覆うような魔法が存在することが分かる。なのて、答えにその宝箱の価値を加算する。

本解法の時間計算量は \(O((N+M) \log (N+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> event;
  for(ll i=0;i<N;i++){
    ll X,C;
    cin >> X >> C;
    event.push_back({X,C});
  }
  for(ll i=0;i<M;i++){
    ll L,R;
    cin >> L >> R;
    event.push_back({L,-1});
    event.push_back({R+1,-2});
  }
  sort(event.begin(),event.end());
  ll h=0,res=0;
  for(auto &nx : event){
    if(nx.second==-1){h++;}
    else if(nx.second==-2){h--;}
    else if(h>0){res+=nx.second;}
  }
  cout << res << "\n";
  return 0;
}