Overview

If we simulate each order naively, we need to check the inventory of all \(M\) types of parts every time, which becomes too slow.
The essence of this problem lies in the fact that “for a successful order, the inventory of all parts decreases by the same amount.” In fact, it is sufficient to only look at the minimum inventory.

Analysis

Whether order \(i\) can produce \(A_i\) units is determined by:

• Whether the inventory of all parts is at least \(A_i\)

Key Insight

When producing \(x\) units of the product, the inventory of every part decreases by \(x\).
In other words, if \(S\) is the total number of units produced from all successful orders so far, the current inventory of part \(j\) is:

\(B_j - S\)

Therefore, the condition for being able to process an order \(A_i\) is:

\(B_j - S \ge A_i \quad (\forall j)\)

This is equivalent to:

\(\min(B_1, B_2, \ldots, B_M) - S \ge A_i\)

This means that instead of managing each part individually,

• We only need to keep track of a single value: the current “minimum inventory.”

Why the Naive Approach Doesn’t Work

With the naive approach, for each order we check all parts, and if the order succeeds, we decrease all parts’ inventories.
This takes \(O(M)\) per order and \(O(NM)\) overall.

Since the constraints are \(N, M \le 5 \times 10^5\), \(O(NM)\) can become extremely large and is far too slow.

How to Solve It

First, compute:

\(\text{remain} = \min(B)\)

This represents “how many more units can be produced such that every part still has enough inventory.”

For each order \(A_i\):

• If \(A_i \le \text{remain}\), the order succeeds
  • Increment the answer by 1
  • \(\text{remain} \leftarrow \text{remain} - A_i\)
• Otherwise, the order is cancelled
  • Nothing changes

This alone correctly handles all orders.

Concrete Example

For example, if

• \(B = [10, 7, 12]\)

then the minimum inventory is \(7\).

Suppose the orders are:

• \(A = [3, 5, 2]\)

Initially: \(\text{remain} = 7\)

1. Order \(3\)
   \(3 \le 7\), so it succeeds
   \(\text{remain} = 7 - 3 = 4\)

2. Order \(5\)
   \(5 > 4\), so it fails
   \(\text{remain}\) stays at \(4\)

3. Order \(2\)
   \(2 \le 4\), so it succeeds
   \(\text{remain} = 4 - 2 = 2\)

Therefore, the number of successful orders is \(2\).

Verifying with the actual part inventories:

• Initial: \([10, 7, 12]\)
• After producing 3: \([7, 4, 9]\)
• Cannot produce 5
• After producing 2: \([5, 2, 7]\)

This indeed matches.

Algorithm

1. Compute the minimum value of array \(B\) and set it as remain.
2. Initialize the answer ans = 0.
3. Process orders from the beginning in order.
   • If \(A_i \le \text{remain}\):
     • ans += 1
     • remain -= A_i
   • Otherwise, do nothing.
4. Output ans.

Complexity

• Time complexity: \(O(N + M)\)
• Space complexity: \(O(1)\) (excluding the input arrays)

Implementation Notes

• There is no need to update each part’s inventory every time. It is sufficient to just maintain min(B).

• When an order fails, the inventory does not change, so remain is not modified either.

• \(A_i\) and \(B_j\) can be up to \(10^9\), but Python’s integers can handle this directly.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    remain = min(B)
    ans = 0
    
    for x in A:
        if x <= remain:
            ans += 1
            remain -= x
    
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.