Overview

Assign each print request to a printer that can handle it, and find the minimum time at which all requests are completed.
We determine “Can all requests be processed by a given time \(x\)?” and use binary search on the answer based on this decision.

Analysis

Printer \(i\) always takes \(T_i\) to process one request.
Therefore, the number of requests printer \(i\) can process by time \(x\) is

\( \left\lfloor \frac{x}{T_i} \right\rfloor \)

requests.

In other words, when time \(x\) is fixed, the problem can be rephrased as follows:

• Printer \(i\) can process at most \( \left\lfloor \frac{x}{T_i} \right\rfloor \) requests
• However, a request with \(P_j\) pages can only be assigned to a printer where \(W_i \geq P_j\)
• Can all requests be assigned?

The key insight here is that if processing is possible by time \(x\), then it is always possible by a longer time \(x+1\) or more.
Therefore, we can binary search on the answer.

Decision Method

Sort the requests in decreasing order of page count, and sort the printers in decreasing order of maximum page capacity \(W_i\).

Requests with more pages have fewer printers that can handle them.
Therefore, it is natural to greedily assign larger requests first to printers with higher capacity.

For example, suppose at a given time \(x\), the processing capacities of the printers are as follows:

Printer	Max Pages \(W_i\)	Processing Capacity
A	10	1
B	8	2
C	4	1

If the page counts of the requests are

\(9, 8, 5, 4\)

then we can assign:

• \(9\) to A
• \(8, 5\) to B
• \(4\) to C

On the other hand, if we consider printers with smaller maximum page capacity first, larger requests may become unassignable later.
Therefore, it is important to “process larger requests using printers with larger \(W_i\) first.”

Why a Naive Approach Is Difficult

Searching for available printers for each request or simulating the actual schedule would be too slow since \(N+M \leq 2 \times 10^5\).

Also, trying all possible assignments causes combinatorial explosion.

Therefore, we take the following approach:

1. Binary search on the answer
2. For a fixed time \(x\), greedily determine whether all requests can be assigned

Algorithm

First, if there exists a request that no printer can handle, it is impossible.

Specifically, if

\( \max P_j > \max W_i \)

then there is no printer that can process that request, so the answer is \(-1\).

Otherwise, we binary search on the answer.

Decision Function ok(x)

Determines whether all requests can be processed by time \(x\).

1. Sort requests in decreasing order of page count
2. Sort printers in decreasing order of \(W_i\)
3. Maintain an index idx pointing to the largest unassigned request
4. For each printer:
   • The number of requests this printer can process by time \(x\) is \(x // T_i\)
   • If the current largest unprocessed request cannot be handled by this printer, then no subsequent printer can handle it either, so it is impossible
   • If it can be handled, assign as many requests as possible to this printer
5. If all requests are assigned, it is possible

The following part of the code performs the decision:

def ok(x):
    idx = 0
    for w, t in ps:
        if idx >= m:
            return True
        cap = x // t
        if cap:
            if js[idx] > w:
                return False
            idx += cap
            if idx >= m:
                return True
    return False

Here, js is the array of requests sorted in decreasing order of page count.
ps is the array of printers sorted in decreasing order of \(W_i\).

If js[idx] > w, the current largest remaining request cannot be processed by this printer.
Furthermore, since all subsequent printers have \(W_i\) that is equal or smaller, no printer can process this request anymore.
Therefore, we can determine it is impossible.

Binary Search

As an upper bound for the answer, consider the case where the fastest printer capable of handling the request with the most pages processes all requests by itself.

hi = min(t for w, t in printers if w >= max_p) * M

This value is always an achievable time.

Then:

• If ok(mid) is true, it might be possible in less time, so set hi = mid
• If false, there is not enough time, so set lo = mid

and perform binary search.

Ultimately, hi is the answer.

Complexity

• Time complexity: \(O(N \log N + M \log M + N \log (M \max T_i))\)
• Space complexity: \(O(N + M)\)

The number of binary search iterations is at most about \(50\).
Each decision only iterates through the printers once, so it is \(O(N)\).

Implementation Notes

• Requests are sorted in decreasing order of page count with jobs.sort(reverse=True).

• Printers are also sorted in decreasing order of \(W_i\) with printers.sort(reverse=True).

• The answer can be as large as \(10^9 \times 2 \times 10^5 = 2 \times 10^{14}\), so 64-bit integers are required.

  • In Python, there is no need to worry about integer overflow.

• In the decision function, instead of assigning requests one by one, we advance by idx += cap to process them in bulk for efficiency.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

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

    printers = []
    max_w = 0
    for _ in range(N):
        w = next(it)
        t = next(it)
        printers.append((w, t))
        if w > max_w:
            max_w = w

    jobs = [next(it) for _ in range(M)]
    max_p = max(jobs)

    if max_p > max_w:
        print(-1)
        return

    jobs.sort(reverse=True)
    printers.sort(reverse=True)

    hi = min(t for w, t in printers if w >= max_p) * M
    lo = 0

    js = jobs
    ps = printers
    m = M

    def ok(x):
        idx = 0
        for w, t in ps:
            if idx >= m:
                return True
            cap = x // t
            if cap:
                if js[idx] > w:
                    return False
                idx += cap
                if idx >= m:
                    return True
        return False

    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid

    print(hi)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.