Overview

Each printer has a “maximum number of pages it can handle” and a “processing time per job.”
We find the minimum time to finish processing all jobs using binary search and a greedy feasibility check.

Analysis

By time \(x\), the number of jobs printer \(i\) can process is

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

jobs.

In other words, whether all jobs can be processed by time \(x\) can be thought of as:

• Printer \(i\) can handle jobs of at most \(W_i\) pages
• It has \(\left\lfloor \frac{x}{T_i} \right\rfloor\) such processing slots

For example, if the printer capabilities are:

Printer	\(W_i\)	\(T_i\)
1	10	3
2	5	2

and \(x = 6\), then:

• Printer 1 can process \(\lfloor 6/3 \rfloor = 2\) jobs
• Printer 2 can process \(\lfloor 6/2 \rfloor = 3\) jobs

Therefore, we can consider that:

• There are 2 slots that can handle up to 10 pages
• There are 3 slots that can handle up to 5 pages

---

Here, we sort the jobs in decreasing order of page count.

Jobs with more pages should be considered first, since fewer printers can handle them.

For example, suppose the jobs are:

\(9, 7, 4\)

The first 2 jobs, namely the 9-page and 7-page jobs, must be processed by printer slots that can handle at least \(7\) pages.

In general, if we sort the jobs in descending order as

\(P_1 \geq P_2 \geq \cdots \geq P_M\)

then the first \(k\) jobs all have at least \(P_k\) pages.

Therefore, for processing to be feasible by time \(x\):

“The total number of processable jobs among printers satisfying \(W_i \geq P_k\)” must be at least \(k\).

If this condition is satisfied for all \(k\), then processing is feasible.

---

Naively searching all possible assignments of jobs to printers would result in an enormous number of combinations and would never finish in time.

Also, simulating the actual scheduling for each time point is complex.

Therefore, we take the following approach:

• Binary search on the answer (time)
• Quickly determine whether processing is feasible at that time

If processing is feasible at time \(x\), then it is always feasible at any time greater than \(x\).
Because of this monotonicity, binary search can be applied.

Algorithm

First, sort all jobs in descending order of page count.

Also, sort the printers in descending order of \(W_i\).

The feasibility function feasible(x) checks whether all jobs can be processed by time \(x\).

The procedure is as follows:

1. Look at jobs in decreasing order of page count
2. Let \(p\) be the page count of the current job
3. Add printers satisfying \(W_i \geq p\)
4. For the added printers, sum up the number of jobs processable by time \(x\): \(\left\lfloor x / T_i \right\rfloor\)
5. If the total processable count is less than the number of jobs seen so far, it is infeasible

In the code, the total processable count is stored in cap.

while (idx < N && printers[idx].first >= p) {
    ll add = x / printers[idx].second;
    if (add > M) add = M;
    cap = min<ll>(M, cap + add);
    idx++;
}

Since printers are sorted in descending order of \(W_i\), each printer is added at most once.

Therefore, a single feasibility check runs in \(O(N + M)\).

---

Finally, we binary search for the answer.

First, if there exists a job that no printer can handle, i.e.,

\( \max P_j > \max W_i \)

then the answer is \(-1\).

Otherwise, among the printers that can handle the job with the maximum page count, using the fastest one guarantees that all jobs can be processed.

If we call that processing time minT, then the answer is at most

\(minT \times M\)

We use this as the upper bound for binary search.

ll ng = 0;
ll ok = minT * M;

• ng: a time at which processing is infeasible
• ok: a time at which processing is feasible

We perform binary search as follows:

while (ok - ng > 1) {
    ll mid = (ng + ok) / 2;
    if (feasible(mid)) ok = mid;
    else ng = mid;
}

Ultimately, ok is the answer.

Complexity

• Time complexity: \(O((N + M) \log (minT \times M))\)
• Space complexity: \(O(N + M)\)

Implementation Notes

If we simply sum up the processable count per printer

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

the total can become extremely large and may overflow.

However, since we need at most \(M\) jobs, the code caps cap at \(M\).

if (add > M) add = M;
cap = min<ll>(M, cap + add);

Also, by sorting both the jobs in descending order and the printers in descending order of \(W_i\), we only need to iterate through the printers once within the feasibility function.

Source Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<pair<ll, ll>> printers(N);
    ll maxW = 0;
    for (int i = 0; i < N; i++) {
        ll W, T;
        cin >> W >> T;
        printers[i] = {W, T};
        maxW = max(maxW, W);
    }

    vector<ll> jobs(M);
    for (int i = 0; i < M; i++) cin >> jobs[i];

    sort(jobs.rbegin(), jobs.rend());

    if (jobs[0] > maxW) {
        cout << -1 << '\n';
        return 0;
    }

    sort(printers.begin(), printers.end(), [](const auto& a, const auto& b) {
        if (a.first != b.first) return a.first > b.first;
        return a.second < b.second;
    });

    ll minT = (ll)4e18;
    for (auto [W, T] : printers) {
        if (W >= jobs[0]) minT = min(minT, T);
    }

    auto feasible = [&](ll x) -> bool {
        ll cap = 0;
        int idx = 0;

        for (int j = 0; j < M; j++) {
            ll p = jobs[j];

            while (idx < N && printers[idx].first >= p) {
                ll add = x / printers[idx].second;
                if (add > M) add = M;
                cap = min<ll>(M, cap + add);
                idx++;
            }

            if (cap < j + 1) return false;
        }

        return true;
    };

    ll ng = 0;
    ll ok = minT * M;

    while (ok - ng > 1) {
        ll mid = (ng + ok) / 2;
        if (feasible(mid)) ok = mid;
        else ng = mid;
    }

    cout << ok << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.