Overview

Under the constraints that at most \(L_i\) books can be inspected each day and the same book can be inspected at most once on the same day, we determine whether each book \(j\) can be inspected at least \(R_j\) times by reducing the problem to checking a necessary and sufficient inequality condition.

Analysis

An inspection plan can be represented as an \(N\) days \(\times\) \(M\) books \(0/1\) matrix (where \(a_{i,j}=1\) means book \(j\) is inspected on day \(i\)):

• Row sums (each day): \(\sum_j a_{i,j} \le L_i\)
• Column sums (each book): \(\sum_i a_{i,j} \ge R_j\)
• Additionally, \(a_{i,j}\in\{0,1\}\) (the same book cannot be inspected multiple times on the same day)

Here, “each book at least \(R_j\) times” is required, but inspecting more than necessary provides no benefit (it only uses up the daily limit). Thus, it suffices to consider whether each book can be inspected exactly \(R_j\) times.

---

Key Observation (Upper Bound Constraint on Subsets)

Consider any subset \(S\) of books (\(|S|=k\)).

• The maximum number of books from \(S\) that can be inspected on day \(i\) is at most \(\min(L_i, k)\)
  (since the total number of books inspectable that day is at most \(L_i\), and there are only \(k\) books in \(S\))
• Therefore, the total number of inspections needed for \(S\), \(\sum_{j\in S} R_j\), must satisfy: [ \sum_{j\in S} Rj \le \sum{i=1}^N \min(L_i, k) ] otherwise it is impossible.

This is a necessary condition, and in fact it is also a sufficient condition (as can be shown via max-flow min-cut or degree conditions for bipartite graphs).

---

How to Check “All Subsets \(S\)”

There are \(2^M\) possible subsets \(S\), making exhaustive enumeration impossible. However, the right-hand side depends only on \(k=|S|\).

Therefore, to maximize the left-hand side \(\sum_{j\in S} R_j\) for a fixed size \(k\), the worst case is choosing the \(k\) books with the largest \(R_j\).
That is, sorting \(R\) in descending order and looking at [ \text{demand}(k)=\sum{t=1}^{k} R{(t)} ] (the sum of the top \(k\) values) is sufficient.

In the end, the condition to check is, for all \(k=1..M\): [ \sum{t=1}^{k} R{(t)} \le \sum_{i=1}^N \min(L_i, k) ]

Naively summing \(N\) terms for the right-hand side each time gives \(O(NM)\), which is too slow. So we compute the right-hand side efficiently.

Algorithm

1. Sort \(L\) in ascending order.

2. Sort \(R\) in descending order.

3. Iterate \(k\) from \(1\) to \(M\), updating and checking the following:

   • \(\text{demand} \leftarrow \text{demand} + R[k-1]\) (sum of the top \(k\) values)
   • Compute \(\sum_i \min(L_i,k)\) (capacity):
     • For those with \(L_i \le k\): \(\min(L_i,k)=L_i\)
     • For those with \(L_i > k\): \(\min(L_i,k)=k\)

   Since \(L\) is sorted in ascending order, we advance a pointer over the range where \(L_i \le k\): - sum_small = sum of \(L_i\) where \(L_i \le k\) - The remaining \((N-idx)\) entries each contribute \(k\)

   Therefore: [ \text{capacity} = \text{sum_small} + (N-idx)\cdot k ] - If \(\text{demand} > \text{capacity}\), it is impossible, so output No.

4. If no violation is found through the end, output Yes.

Complexity

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

Implementation Notes

• The check must be performed for all \(k\) (checking only \(k=M\) is insufficient).

• Computing \(\sum_{i=1}^N \min(L_i,k)\) in \(O(N)\) each time is too slow, so the key technique is sorting \(L\) in ascending order to avoid a nested loop.

• \(R\) is sorted in descending order and its prefix sums are taken in order to construct the worst-case selection of \(k\) books.

  Source Code

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)
    L = [next(it) for _ in range(N)]
    R = [next(it) for _ in range(M)]

    L.sort()
    R.sort(reverse=True)

    idx = 0
    sum_small = 0  # sum of L_i <= k
    demand = 0

    for k in range(1, M + 1):
        demand += R[k - 1]

        while idx < N and L[idx] <= k:
            sum_small += L[idx]
            idx += 1

        capacity = sum_small + (N - idx) * k
        if demand > capacity:
            print("No")
            return

    print("Yes")

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.