Overview

This is a problem where Takahashi harvests fruits using stepladders in a given order, maximizing the total deliciousness obtained.

Analysis

In this problem, for each harvesting opportunity, the optimal strategy is to “choose the most delicious fruit among those currently reachable.” However, if we naively perform a linear search for the maximum deliciousness each time, the worst case becomes \(O(NM)\), which cannot be processed within the time limit due to the large constraints (TLE).

Therefore, we consider using a priority queue (max heap) to efficiently manage the “currently selectable fruits.”
Furthermore, since the stepladder heights \(L_j\) are not necessarily given in ascending order, by sorting and processing them in order of stepladder height, we can gradually increase the set of selectable fruits.

Specifically: - Sort the fruits in ascending order of height \(D_i\). - Process the harvesting opportunities in ascending order of stepladder height \(L_j\). - At each harvesting opportunity, add all fruits reachable with the current stepladder height to the heap. - Extract the fruit with the highest deliciousness from the heap and select it.

By doing this, each fruit enters the heap only once, and at each harvesting opportunity we only extract the maximum element, so the overall operation runs efficiently.

Algorithm

1. Sort the fruit list in ascending order of height \(D_i\).
2. Sort the stepladder heights \(L_j\) of harvesting opportunities in ascending order and process them in that order.
3. Prepare a max heap (in Python, use a min heap with negated values), and for each harvesting opportunity, do the following:
   • Add all fruits reachable with the current stepladder height \(L_j\) to the heap.
   • Extract the maximum value from the heap (the most delicious fruit) and add it to the answer.
4. After processing all harvesting opportunities, output the total value.

Example

For example, if the fruits are \((D, V) = [(1, 3), (2, 5), (3, 2)]\) and the stepladders are \(L = [2, 3]\):

• Sorted fruits: \([(1, 3), (2, 5), (3, 2)]\)
• Stepladders in ascending order: \([2, 3]\)

1st harvest (\(L=2\)): Can choose from fruits at heights 1 and 2, select deliciousness 5 → total 5
2nd harvest (\(L=3\)): Fruit at height 3 (deliciousness 2) becomes selectable → total 7

Therefore the maximum value is 7.

Complexity

• Time complexity: \(O(N \log N + M \log M)\)
  • Sorting fruits: \(O(N \log N)\)
  • Sorting harvesting opportunities: \(O(M \log M)\)
  • Heap operations (at most N insertions, M extractions): \(O((N + M) \log N)\)
• Space complexity: \(O(N + M)\)

Implementation Notes

• Python’s heapq is a min heap, so to use it as a max heap, manage elements by negating them.

• Since adding fruits and harvesting must be done respecting the sorted order, both lists need to be sorted in advance.

• Don’t forget to check whether the heap is empty (if nothing can be taken, skip).

  Source Code

import heapq
import sys

input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    fruits = []
    idx = 2
    for _ in range(N):
        D = int(data[idx])
        V = int(data[idx+1])
        fruits.append((D, V))
        idx += 2
    
    L = list(map(int, data[idx:idx+M]))
    
    # 果物を高さDでソート
    fruits.sort()
    
    # 収穫チャンスを高さLでソートしたインデックスを取得
    sorted_indices = sorted(range(M), key=lambda x: L[x])
    
    # 各収穫チャンスで選べる果物候補を管理するためのヒープ
    heap = []
    fruit_idx = 0
    total_deliciousness = 0
    
    # 高さが低い収穫チャンスから順に処理
    for i in sorted_indices:
        l = L[i]
        # 現在の脚立の高さで届く果物を全てヒープに追加（おいしさを負にして最大ヒープ）
        while fruit_idx < N and fruits[fruit_idx][0] <= l:
            heapq.heappush(heap, -fruits[fruit_idx][1])
            fruit_idx += 1
        
        # その収穫チャンスで最もおいしさの高い果物を選択
        if heap:
            total_deliciousness += -heapq.heappop(heap)
    
    print(total_deliciousness)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.