Overview

Each truck has the condition “can carry at most \(C_i\) items, each weighing at most \(E_i\).” We can think of a truck as “a box with \(C_i\) slots, each with a weight limit,” and we want to find the maximum number of items that can be assigned to these slots.

Analysis

Key Insight

• The constraint is only “each individual item’s weight \(D_j \le E_i\)” — there is no total weight constraint.
• Therefore, truck \(i\) can be thought of as “providing \(C_i\) slots with upper limit \(E_i\)” (all slots from the same truck have the same constraint).
• The problem then becomes:
  Assign each item (weight \(D_j\)) to a slot whose upper limit is at least \(D_j\), one item per slot
  — a maximum matching problem (where multiple slots can share the same upper limit).

Why a Naive Approach Is Too Slow

For example, if we naively check for each item “which truck can hold it and has remaining capacity”: - Checking all \(N\) trucks for each of the \(M\) items gives \(O(NM)\), which is far too slow (up to \(4\times 10^{10}\)). - Even managing with priority queues or multisets, designing around “which truck to assign each item to” tends to make implementation complex.

How to Solve It (Greedy Direction)

Heavier items have fewer slots they can fit into.
Therefore, it is natural to process items in decreasing order of weight and assign them to a slot immediately if one is available.

This ordering is important: if we defer heavier items, lighter items may use up slots first, leaving no room for heavier items later.

Furthermore, in this problem, when processing in decreasing weight order: - “Slots that can hold the current item of weight \(w\)” are all slots with \(E_i \ge w\) - The next item to be processed has equal or lesser weight, so any unused slots remain usable in the future

This means we don’t need to distinguish “which truck’s slot was used” — it suffices to just track the total number of available slots avail.

Algorithm

1. Prepare trucks as pairs \((E_i, C_i)\) and sort them in decreasing order of \(E_i\).
2. Sort item weights \(D_j\) in decreasing order as well.
3. Process items one by one from heaviest to lightest (let the current weight be \(w\)):
   • Among trucks not yet processed, take all those satisfying \(E_i \ge w\) and add their slot counts \(C_i\) to avail.
   • If avail > 0, this item can be placed in some slot, so do avail -= 1 and increment the answer by 1.
4. The final count is the maximum number of deliveries.

Concrete example: - Trucks: \((E,C)=(10,1),(6,2)\), Items: \([9,6,6,5]\) - Process items in decreasing weight order:
- 9: Slots with \(E\ge9\): 1 slot from the truck with limit 10 → avail=1 → use it, avail=0, ans=1
- 6: Add 2 slots from the truck with \(E=6\) → avail=2 → use one, avail=1, ans=2
- 6: avail=1 → use it, avail=0, ans=3
- 5: No new slots, avail=0 → cannot place, ans=3

Complexity

• Time complexity: \(O((N+M)\log(N+M))\) for sorting, \(O(N+M)\) for the scan
• Space complexity: \(O(N+M)\) for input arrays and sorting

Implementation Notes

• Sort both trucks and items in decreasing order. For the truck side, use a pointer ti to advance through “trucks satisfying \(E_i \ge w\)” from the front, visiting each truck only once (avoiding a nested loop).

• avail represents “the remaining number of slots that can hold the current item,” so we do avail -= 1 each time a slot is used.

• Since \(N,M \le 2\times10^5\), in Python I/O can become a bottleneck. Reading integers efficiently with sys.stdin.buffer.read() as shown in the provided code ensures stable performance.

  Source Code

import sys

def int_iter():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break
        num = 0
        while i < n and data[i] > 32:
            num = num * 10 + (data[i] - 48)
            i += 1
        yield num

it = int_iter()
N = next(it)
M = next(it)

trucks = [(next(it), next(it)) for _ in range(N)]
items = [next(it) for _ in range(M)]

trucks.sort(key=lambda x: x[0], reverse=True)
items.sort(reverse=True)

avail = 0
ans = 0
ti = 0

for w in items:
    while ti < N and trucks[ti][0] >= w:
        avail += trucks[ti][1]
        ti += 1
    if avail > 0:
        avail -= 1
        ans += 1

sys.stdout.write(str(ans) + "\n")

---

This editorial was generated by gpt-5.2-high.