Summary

This is a problem where we need to assign each student to a bus in order to minimize the number of uncomfortable students.
In fact, since we can simply put everyone on the bus with the highest ceiling, the answer is the number of students whose height is strictly greater than that of the tallest bus.

Analysis

The important conditions in this problem are:

• There is no limit on the number of people assigned to a single bus.
• There can be buses with no students assigned to them.
• Students in the same class must ride the same bus.

At first glance, it seems necessary to determine which bus to assign each class to.
However, since there is no capacity limit on the buses, we can safely put all students on the same bus.

Then, which bus is the optimal choice to put everyone on?

Naturally, putting everyone on the bus with the highest ceiling will minimize the number of uncomfortable students.
Let \(D_{\max}\) be the maximum ceiling height among all buses. Then:

• Students with height \(H_j \leq D_{\max}\) will not feel uncomfortable if they ride the tallest bus.
• Students with height \(H_j > D_{\max}\) will feel uncomfortable regardless of which bus they ride.

Therefore, the minimum number of uncomfortable students is the number of students who satisfy

\[ H_j > D_{\max} \]

For example, if the ceiling heights of the buses are

\[ 150, 180, 170 \]

then the height of the tallest bus is \(180\).
If we put everyone on the bus of height \(180\), all students with a height of \(180\) or less will be comfortable.
Only students with a height of \(181\) or more will be uncomfortable in any bus.

If we naively think about “which bus to assign to each class”, the number of combinations becomes extremely large, leading to high computational complexity.
However, once we realize that we can put everyone on the same bus, we do not need to consider class names or class divisions at all.

Algorithm

1. Find the maximum value \(D_{\max}\) of the bus ceiling heights \(D_i\).
2. For each student, check if their height \(H_j\) is strictly greater than \(D_{\max}\).
3. Count the number of students satisfying \(H_j > D_{\max}\).
4. Output that count.

The class name \(S_j\) does not affect the answer.
Although students of the same class must ride the same bus, this condition is automatically satisfied if we put everyone on the tallest bus.

Complexity

• Time Complexity: \(O(N + M)\)
• Space Complexity: \(O(1)\)

There is no need to store all the bus heights; knowing only the maximum value is sufficient.
Furthermore, we can process the students one by one and count the answer on the fly, so no additional arrays are required.

Implementation Details

We only use the maximum value of the bus ceiling heights.

max_d = max(map(int, input().split()))

After that, we read the students one by one, and if their height is greater than max_d, we add 1 to the answer.

if int(h) > max_d:
    ans += 1

We need to read the class name s, but we do not use it for the check.

Source Code

import sys

def main():
    input = sys.stdin.buffer.readline

    N, M = map(int, input().split())
    max_d = max(map(int, input().split()))

    ans = 0
    for _ in range(M):
        s, h = input().split()
        if int(h) > max_d:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.