Overview

A product that can satisfy every day’s budget \(S_j\) (i.e., can be bought every day) is one whose price \(R_i\) is “at most the minimum budget.” We count the number of such products.

Analysis

The condition is “\(R_i \le S_j\) for all days \(j\).” Due to the nature of inequalities, this means:

• \(R_i \le S_1\)
• \(R_i \le S_2\)
• \(\dots\)
• \(R_i \le S_M\)

must all hold simultaneously.

The key insight here is that if we let \(B = \min(S_1,\dots,S_M)\) be the minimum budget among all \(S_j\), then:

• \(R_i \le S_j\) holds for all days
  \(\Longleftrightarrow\) In particular, we can buy it even on the day with the smallest budget (\(R_i \le B\))

In other words, the check \(R_i \le \min S\) alone is sufficient.

Naively checking all days \(j\) for each product \(i\) would be \(O(NM)\), which at maximum is \(10^6 \times 10^6 = 10^{12}\) comparisons — far too slow.
Instead, we compute \(\min S\) just once beforehand, then simply compare each product’s price against it and count.

Example: - If budgets are \(S = [300, 250, 400]\), then \(\min S = 250\) - Among prices \(R = [200, 260, 250]\), those at most \(250\) are \(200\) and \(250\) — two products
\(\Rightarrow\) The answer is 2

Algorithm

1. Read the \(M\) budget values \(S_j\) from input while computing the minimum \(B=\min S\).
2. For the \(N\) prices \(R_i\), count how many satisfy \(R_i \le B\).
3. Output that count.

Complexity

• Time complexity: \(O(N+M)\)
• Space complexity: \(O(N)\) (to store the prices. This can be reduced to \(O(1)\) if we count while reading without storing them.)

Implementation Notes

• Since \(N, M \le 10^6\) and the input is very large, we read everything at once using sys.stdin.buffer.read() and manually parse the integers for speed.

• Since we only need the minimum of the budgets, we update min_budget while reading without storing them in an array.

• Prices are stored in an array('I') (C-style integer array), which is more memory-efficient than a regular Python list.

  Source Code

import sys
from array import array

def main():
    data = sys.stdin.buffer.read()
    ndata = len(data)
    idx = 0

    def next_int():
        nonlocal idx
        while idx < ndata and data[idx] <= 32:
            idx += 1
        num = 0
        while idx < ndata and data[idx] > 32:
            num = num * 10 + (data[idx] - 48)
            idx += 1
        return num

    N = next_int()
    M = next_int()

    prices = array('I')
    prices_extend = prices.append
    for _ in range(N):
        prices_extend(next_int())

    min_budget = 10**9 + 1
    for _ in range(M):
        s = next_int()
        if s < min_budget:
            min_budget = s

    cnt = 0
    for r in prices:
        if r <= min_budget:
            cnt += 1

    sys.stdout.write(str(cnt))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.