Overview

This is a problem of finding the number of products, out of \(N\) types, that can be purchased within the snack budget of every single day.

Analysis

The key point is how to handle the condition “for every day, the product price \(R_i\) must be at most the budget \(S_j\).”

A naive approach would be to check, for each product \(i\), whether \(R_i \leq S_j\) holds for all \(M\) days using a loop. However, this method requires \(M\) checks to determine a single product, resulting in \(N \times M\) total computations. Since the constraints are \(N, M \leq 10^6\), the number of computations can reach up to \(10^{12}\), which would result in TLE (Time Limit Exceeded).

The crucial observation here is that the condition “the price must be at most every budget \(S_j\)” can be rephrased as “the price must be at most the minimum of all budgets \(S_j\).” For example, if the budgets on different days are 300 yen, 200 yen, and 400 yen, then a product that can be purchased on every day must have a price of at most 200 yen (the minimum), which is the most restrictive budget. Therefore, by computing the minimum of the budgets \(S_j\) in advance, we can determine whether each product satisfies the condition with just a single comparison.

Algorithm

1. Find the minimum among the daily snack budgets \(S_1, S_2, \ldots, S_M\), and call it min_S.
2. Initialize a counter ans to \(0\) to count the number of products that satisfy the condition.
3. For each product price \(R_1, R_2, \ldots, R_N\), compare it with min_S in order.
4. If \(R_i \leq\) min_S, then that product can be purchased on every day, so add \(1\) to ans.
5. After checking all products, output ans.

Complexity

• Time complexity: \(O(N + M)\)
  • Finding the minimum budget takes \(O(M)\), and checking each product price takes \(O(N)\), so the overall complexity is \(O(N + M)\).
• Space complexity: \(O(N + M)\)
  • Since all input data is stored in memory as arrays (lists), space proportional to the input size is required.

Implementation Notes

• Fast I/O: Since \(N\) and \(M\) can be as large as \(10^6\), reading input line by line using Python’s standard input() may cause the program to exceed the time limit just from input processing alone. As shown in the solution code, using sys.stdin.read().split() to read all input at once and convert it into a list is an effective technique.

• Using slices: Since the read data becomes a single flat list data, the product prices can be easily extracted as data[2 : 2+N] and the budgets as data[2+N : ] using slices.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.read().split()))
    if not data:
        return
    
    N = data[0]
    
    min_S = min(data[2+N:])
    
    ans = 0
    for r in data[2:2+N]:
        if r <= min_S:
            ans += 1
            
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.