この問題において、脚立が配られる順番は答えに影響しません（最適な収穫のしかたにおいてそれぞれの脚立で収穫する果物は、配られ方によらずそれぞれの脚立で収穫することができます）。 よって、脚立が配られる順番を好きに並べ替えてよいことがわかります。

この問題は、イベントソートを使って解くことができます。

具体的には、次のような出来事を考えます。

• 高さ \(D\) 、おいしさ \(V\) の果物が追加される。
• 高さ \(L\) の脚立が追加される。

これらの出来事を高さの昇順に並べ、脚立が追加されるごとにその時点までに追加された（かつまだ収穫されていない）果物のうちおいしさが最大であるものを収穫するのが最適です。

現在収穫することができる果物の集合をヒープなどで管理することで、\(O((N+Q)\log N)\) 時間でこの問題を解くことができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <queue>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    // (高さ, 果物か脚立か, 果物ならおいしさ) の列
    vector<tuple<int, int, int>> event;
    for (int i = 0; i < N; ++i) {
        int D, V;
        cin >> D >> V;
        event.emplace_back(D, 0, V);
    }
    for (int i = 0; i < M; ++i) {
        int L;
        cin >> L;
        event.emplace_back(L, 1, 0);
    }

    // 高さの昇順に並べる
    ranges::sort(event);

    // 収穫できる果物のおいしさをヒープで管理する
    priority_queue<int> pq;

    long ans = 0;
    for (auto [_, type, value] : event) {
        if (type == 0) { // 果物なら
            pq.emplace(value); // ヒープに追加
        } else { // 脚立なら
            if (!empty(pq)) { // 収穫できる果物があれば
                ans += pq.top(); // おいしさ最大の果物を収穫する
                pq.pop();
            }
        }
    }
    cout << ans << endl;
    return 0;
}

from heapq import heappush, heappop


N, M = map(int, input().split())

# (高さ, 果物か脚立か, 果物ならおいしさ) の列
event = []
for i in range(N):
    D, V = map(int, input().split())
    event.append((D, 0, V))
for L in map(int, input().split()):
    event.append((L, 1, 0))

# 高さの昇順に並べる
event.sort()

# 収穫できる果物のおいしさをヒープで管理する
pq = []

ans = 0
for _, type, value in event:
    if type == 0: # 果物なら
        heappush(pq, -value) # ヒープに追加
    else: # 脚立なら
        if len(pq) > 0: # 収穫できる果物があれば
            ans += -heappop(pq) # おいしさ最大の果物を収穫する

print(ans)