Overview

This problem asks for the minimum time at which all requests can be completed. It can be efficiently solved by performing binary search on the answer time \(X\), and quickly solving the decision problem “Can all requests be processed within time \(X\)?” using sorting and prefix sums.

Analysis

1. Reduction to a Decision Problem (Binary Search)

The optimization problem “find the minimum time at which all requests can be completed” is difficult to solve directly. However, if we fix a time \(X\) and replace it with the decision problem “Can all requests be processed within time \(X\)?” (a boolean), the following monotonicity holds: - If time \(X\) is sufficiently large, all requests can be processed (True). - If time \(X\) is too small, not all requests can be processed (False).

Therefore, by creating a function check(X) that solves this decision problem, we can efficiently find the minimum time \(X\) using binary search.

2. Processing Capacity at Time \(X\)

Given time \(X\), the maximum number of requests that printer \(i\) can process is \(\lfloor X / T_i \rfloor\) (rounded down).

3. Determining Feasibility of Assignment (Sorting and Prefix Sums)

There is a constraint on which printer a request can be assigned to: “capacity \(W_i \ge\) page count \(P_j\)”. To organize this, we sort printers in descending order of capacity and requests in descending order of page count.

After sorting, consider requests \(0, 1, \dots, j\) (a total of \(j+1\) requests) from the largest. - Since they are sorted in descending order of page count, all \(j+1\) of these requests have a page count of at least \(P_j\). - Only printers with capacity at least \(P_j\) can process these requests. - Since printers are also sorted in descending order of capacity, the printers that can handle these requests are those from the beginning up to some specific index \(k\) (printers \(0 \dots k-1\)).

For all these requests to be processed, “the total processing capacity of the eligible printers must be at least the number of requests \(j+1\)” must hold for all \(j\).

Specifically, if we let \(S\) be the prefix sum of printer processing capacities, the assignment is feasible if the following holds for each \(j\): $\(S[\text{number of printers that can process request } j] \ge j + 1\)$

This check can be performed in \(O(1)\) per \(j\) by precomputing the prefix sums, giving \(O(N + M)\) overall.

---

Algorithm

Preprocessing

1. Feasibility check: If the maximum request page count \(\max(P)\) exceeds the maximum printer capacity \(\max(W)\), processing is impossible regardless of assignment, so immediately output -1.
2. Sorting: Sort printers in descending order of capacity \(W_i\), and requests in descending order of page count \(P_j\).
3. Computing boundary indices (Two-pointer method): For each request \(j\), precompute how many printers from the beginning can process that request (i.e., have capacity at least \(P_j\)) (idx_plus_1[j]) using the two-pointer technique.
4. Excluding unusable printers: Printers that cannot process even the smallest request (insufficient capacity) will never be used in any assignment, so they are excluded (ignored) in advance.

Binary Search

• Search range:
  • low = 0
  • high = (the processing time of the fastest printer among those that can process the largest request) × M (worst-case time if one printer handles all requests)
• Decision function check(X):
  1. Compute the maximum number of requests each printer can process at time \(X\), i.e., \(\lfloor X / T_i \rfloor\), and calculate the prefix sum \(S\).
  2. For each request \(j\) (\(0 \le j < M\)), if there exists any \(j\) such that \(S[\text{idx\_plus\_1}[j]] < j + 1\), return False.
  3. If the condition is satisfied for all \(j\), return True.

---

Complexity

• Time complexity: \(O((N + M) \log(\text{high}))\)

  • Sorting takes \(O(N \log N + M \log M)\).
  • Precomputation using the two-pointer method takes \(O(N + M)\).
  • The number of binary search steps is \(O(\log(\text{high}))\), and the decision function check(X) in each step runs in \(O(N + M)\). Under the overall constraints, \(\log(\text{high})\) is at most around \(60\), which is well within the time limit.

• Space complexity: \(O(N + M)\)

  • This is the memory required to store the arrays for printer and request information, as well as the prefix sum array and index array.

---

Implementation Notes

• Utilizing the two-pointer technique: When finding the boundary of printers that can process each request, instead of calling binary search (bisect) multiple times, we exploit the descending-order sorted property and scan in one direction using the two-pointer technique, achieving \(O(N + M)\) efficiently.

• Estimating the worst case: The initial upper bound high for the binary search is set to \(T_{\min} \times M\), the time for the fastest printer capable of handling the largest request to process all requests alone, keeping the search range to the necessary minimum.

  Source Code

import sys


def solve():
    # Fast I/O
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    M = int(data[1])

    printers = []
    idx_data = 2
    for _ in range(N):
        w = int(data[idx_data])
        t = int(data[idx_data + 1])
        printers.append((w, t))
        idx_data += 2

    P = []
    for _ in range(M):
        P.append(int(data[idx_data]))
        idx_data += 1

    # Preliminary check: if the largest job is larger than the largest printer capacity
    max_P = max(P)
    max_W = max(w for w, t in printers)
    if max_P > max_W:
        print(-1)
        return

    # Sort printers and jobs in descending order
    printers.sort(key=lambda x: x[0], reverse=True)
    P.sort(reverse=True)

    W = [w for w, t in printers]
    T = [t for w, t in printers]

    # Two-pointer approach to find the number of eligible printers for each job
    idx_plus_1 = [0] * M
    i = -1
    for j in range(M):
        pj = P[j]
        while i + 1 < N and W[i + 1] >= pj:
            i += 1
        idx_plus_1[j] = i + 1

    # Optimization: Only consider printers that can process at least the smallest job
    limit = idx_plus_1[-1]
    T_limit = T[:limit]

    # Find the minimum time T_i among printers capable of processing the largest job
    k = idx_plus_1[0]
    T_min = min(T[:k])

    # Binary search range
    high = T_min * M
    low = 0

    j_plus_1 = list(range(1, M + 1))
    S = [0] * (limit + 1)

    # Feasibility check for a given time X
    def check(X):
        curr = 0
        for i in range(limit):
            curr += X // T_limit[i]
            S[i + 1] = curr

        for j in range(M):
            if S[idx_plus_1[j]] < j_plus_1[j]:
                return False
        return True

    # Binary search for the minimum time
    while high - low > 1:
        mid = (low + high) // 2
        if check(mid):
            high = mid
        else:
            low = mid

    print(high)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.