Overview

The number of parts required for each order is “the same quantity for all parts,” so in fact you only need to look at the part with the minimum stock to determine feasibility.
By tracking the cumulative number of products produced and processing each order sequentially, this can be solved efficiently.

Analysis

In this problem, every time \(x\) products are made, the stock of all parts decreases by \(x\).
In other words, at any point, the stock of each part is:

• Remaining stock of part \(j\) = \(B_j - (\text{total number produced so far})\)

The key observation here is:

• The condition for accepting order \(i\) (requiring \(A_i\) units) is
  for all \(j\):
  \(B_j - used \ge A_i\)
• This is equivalent to
  \(used + A_i \le B_j \ (\forall j)\)
• Therefore
  \(used + A_i \le \min_j B_j\)

In other words, the only value needed for the decision is \(\min(B)\).
There is no need to check every part each time.

---

Naively “checking all \(M\) types for each order” would be \(O(NM)\),
which at maximum is \(5\times10^5 \times 5\times10^5\), far too slow.

Instead:

• Compute the minimum stock min_b = min(B) in advance
• used = total number of products produced for accepted orders so far
• For each order \(a\):
  if used + a <= min_b, accept it (used += a, ans += 1)
  otherwise, cancel it

This allows each order to be processed in \(O(1)\).

Algorithm

1. Read the input.
2. Compute min_b = min(B).
3. Initialize used = 0, ans = 0.
4. Process the order sequence A from the beginning:
   • If used + a <= min_b, the order can be fulfilled:
     • used += a
     • ans += 1
   • Otherwise, cancel (do nothing).
5. Output ans.

Complexity

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

Implementation Notes

• used and used + a can be as large as approximately \(5\times10^5 \times 10^9\), so depending on the language, 64-bit integers may be required (Python handles this automatically with arbitrary precision integers).

• Don’t forget that when an order is cancelled, the stock does not decrease (i.e., used is not incremented).

  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()))

    min_b = min(B)
    used = 0
    ans = 0

    for a in A:
        if used + a <= min_b:
            used += a
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.