Overview

For each subject, calculate the required study time when the current score falls short of the passing score, and find the total.

Analysis

The key points of this problem are as follows:

• Each subject is independent. Studying for one subject does not affect any other subject.
• Subjects with a score of \(T\) or above require no studying; only subjects with scores below \(T\) need to be studied.
• The deficit for subject \(i\) is \(T - A_i\) points, and it takes \(C_i\) hours to raise the score by \(1\) point, so the required study time for that subject is \((T - A_i) \times C_i\).

Let’s verify with a concrete example.

For instance, suppose \(N = 3\), \(T = 80\) with the following input:

• Subject 1: \(60 < 80\), so \((80 - 60) \times 3 = 60\) hours needed
• Subject 2: \(90 \geq 80\), so no studying needed (\(0\) hours)
• Subject 3: \(70 < 80\), so \((80 - 70) \times 2 = 20\) hours needed

Total: \(60 + 0 + 20 = 80\) hours

Since this problem can be solved by simply iterating through each subject in order, no special algorithm is needed. A straightforward approach directly yields the optimal solution.

Algorithm

1. Read \(N\) and \(T\).
2. Initialize total study time to \(0\).
3. For each subject \(i\), read the score \(A_i\) and cost \(C_i\).
   • If \(A_i < T\), add the deficit \((T - A_i) \times C_i\) to the total.
   • If \(A_i \geq T\), do nothing.
4. Output the total study time.

Complexity

• Time complexity: \(O(N)\) — each subject is examined exactly once
• Space complexity: \(O(1)\) — only a variable to hold the total is used (no array needed since input is read on the fly)

Implementation Notes

• Make sure not to forget the if A < T conditional branch so that study time is not added when \(A_i \geq T\). If you unconditionally add \((T - A_i) \times C_i\), a negative value would be added when \(A_i > T\), leading to an incorrect answer.

• The output is the minimum total study time, printed on a single line.

  Source Code

N, T = map(int, input().split())
total = 0
for _ in range(N):
    A, C = map(int, input().split())
    if A < T:
        total += (T - A) * C
print(total)

This editorial was generated by claude4.6opus-thinking.