Overview

This problem asks us to assign a printing machine with a printable range \([L_j, R_j]\) to each order’s width \(W_i\).
If we can determine whether “all orders can be printed in \(D\) days,” we can find the answer using binary search.

Analysis

First, the height \(H_i\) does not affect the assignment of printing machines, so we can ignore it.
Also, since orders with the exact same width \(W\) can be printed by the same set of printing machines, we can sum up their quantities and process them together.

---

Feasibility in \(D\) Days

Given \(D\) days, each printing machine can print at most \(D\) sheets.
Therefore, each printing machine \(j\) can be considered as a resource with:

• Printable width range: \([L_j, R_j]\)
• Capacity: \(D\) sheets

In other words, the problem reduces to: “Can we allocate the required number of sheets for each width \(W\) to the capacity of the printing machines whose ranges cover \(W\)?”

---

Why a Naive Approach is Too Slow

Checking all pairs of orders and printing machines would take up to \(O(NM)\) time.
Since \(N+M \leq 10^5\), this will result in a Time Limit Exceeded (TLE).

However, because the constraint for each printing machine is an interval \([L_j, R_j]\) on the width, we can process them efficiently by examining the widths in ascending order.

---

Key Idea of the Greedy Approach

We process the widths in ascending order.

When processing a certain width \(x\), the printing machines that are already available are those satisfying \(L_j \leq x\).
Among them, any printing machine with \(R_j < x\) cannot be used for the current width or any subsequent (larger) widths, so we can discard them.

Among the remaining available printing machines, it is optimal to use the ones with the smallest \(R_j\) first.

The reason is as follows. Suppose that for the current width \(x\), we can use:

• A printing machine with range \([1, 5]\)
• A printing machine with range \([1, 10]\)

In this case, we should prioritize using the \([1, 5]\) machine.
This is because the \([1, 10]\) machine might be useful for larger widths later, whereas the \([1, 5]\) machine will become unusable sooner.

This is a classic “earliest deadline first” greedy strategy.

---

Why Binary Search Works

If it is possible to print everything in \(D\) days, it is always possible to do so in \(D+1\) days.
Thus, the feasibility is monotonic with respect to the number of days.

Therefore, we can find the minimum number of days using binary search.

Algorithm

First, we aggregate orders with the same width.

Example:

Width	Quantity
\(3\)	\(5\)
\(3\)	\(2\)
\(7\)	\(4\)

This can be treated as:

Width	Quantity
\(3\)	\(7\)
\(7\)	\(4\)

---

Feasibility Function feasible(days)

This function determines whether all orders can be printed in days days.

1. Process the order widths in ascending order.
2. Sort the printing machines in ascending order of \(L_j\).
3. For the current width \(x\), add printing machines with \(L_j \leq x\) to the candidates.
4. Prioritize using the candidate printing machines with smaller \(R_j\).
5. If we cannot allocate all the required sheets, return False.
6. If all sheets are successfully allocated, return True.

Since we want to retrieve candidate printing machines in ascending order of \(R_j\), we use a priority queue.

We store the following in the priority queue:

\[ (R_j, \text{remaining capacity}) \]

---

Checking for Impossibility

Let the total number of sheets be:

\[ S = \sum C_i \]

If it is impossible to print everything even in \(S\) days, then it is fundamentally impossible.
In this case, we output \(-1\).

With \(S\) days, each printing machine can print up to \(S\) sheets.
If it is still impossible, it means some widths cannot be printed by any available machine, making it fundamentally impossible.

---

Searching for the Minimum Days

The lower bound of the answer, based on the total printing capacity, is:

\[ \left\lceil \frac{S}{M} \right\rceil \]

The upper bound is \(S\).
Therefore, we perform a binary search within this range.

Complexity

Let \(K\) be the number of unique widths, and \(S = \sum C_i\) be the total number of sheets.
Note that \(K \leq N\).

• Sorting: \(O((N+M)\log(N+M))\)
• Each feasibility check: \(O((K+M)\log M)\)
• Number of binary search iterations: \(O(\log S)\)

Thus, the overall complexity is:

• Time Complexity: \(O((N+M)\log(N+M) + (N+M)\log M \log S)\)
• Space Complexity: \(O(N+M)\)

Under the constraints, \(S \leq 10^9\), so the binary search runs at most about \(30\) times.

Implementation Points

• Although \(H_i\) is provided in the input, it does not affect the assignment, so we can ignore it.

• For orders with the same width \(W_i\), we can sum up their quantities using a hash map (dictionary).

• In the priority queue, we store the “right endpoint \(R_j\)” and the “remaining capacity” for each printing machine.

• Any printing machine with \(R_j < x\) for the current width \(x\) will not be usable in the future, so we discard it.

• Since the number of sheets and days can be up to \(10^9\), you need to use 64-bit integers (such as long long in C++) depending on the programming language.

  Source Code

import sys
import heapq

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

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

    demand_dict = {}
    total = 0
    for _ in range(N):
        w = next(it)
        _h = next(it)
        c = next(it)
        demand_dict[w] = demand_dict.get(w, 0) + c
        total += c

    machines = []
    for _ in range(M):
        l = next(it)
        r = next(it)
        machines.append((l, r))

    demands = sorted(demand_dict.items())
    W = [x for x, _ in demands]
    C = [c for _, c in demands]
    K = len(W)

    machines.sort()
    L = [l for l, _ in machines]
    R = [r for _, r in machines]

    def feasible(days):
        heap = []
        push = heapq.heappush
        pop = heapq.heappop
        p = 0
        m = M
        Ls = L
        Rs = R
        heap_local = heap

        for idx in range(K):
            x = W[idx]
            d = C[idx]

            while p < m and Ls[p] <= x:
                push(heap_local, (Rs[p], days))
                p += 1

            while d > 0:
                while heap_local and heap_local[0][0] < x:
                    pop(heap_local)

                if not heap_local:
                    return False

                r, cap = pop(heap_local)
                if cap > d:
                    cap -= d
                    d = 0
                    push(heap_local, (r, cap))
                else:
                    d -= cap

        return True

    if not feasible(total):
        print(-1)
        return

    low = max(1, (total + M - 1) // M)
    high = total

    while low < high:
        mid = (low + high) // 2
        if feasible(mid):
            high = mid
        else:
            low = mid + 1

    print(low)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.