Overview

This problem asks you to calculate the minimum total study time by summing up “deficit points × study time per point” for each subject whose score falls short of the passing score \(T\).

Analysis

The key observation is that “the required study time is determined independently for each subject.” If the score for subject \(i\) is \(A_i < T\), then the additional points needed are \(T - A_i\), and since it takes \(C_i\) hours to raise the score by 1 point, the time required for that subject is uniquely determined as: - \((T - A_i) \times C_i\)

Conversely, if \(A_i \ge T\), no additional study is needed, so it takes \(0\) hours.

No optimization such as “which subject to study first” or “how to allocate time wisely” is needed here. This is because the deficit for each subject must be fully covered, and studying one subject cannot compensate for another subject’s shortfall.

If you naively “simulate increasing scores by 1 point at a time,” the worst case would be up to \(10^4\) points per subject × \(10^5\) subjects, resulting in approximately \(10^9\) operations, which is impractical (TLE). By computing the deficit collectively using multiplication, each subject only needs to be processed once.

(Example) If \(T=80\) and a subject has \(A=75, C=3\), the deficit is \(5\) points, so the required time is \(5\times3=15\). Sum this across all subjects.

Algorithm

1. Read \(N, T\) from input.
2. Initialize total = 0.
3. For each subject, read \((A_i, C_i)\):
   • If \(A_i < T\), then total += (T - A_i) * C_i
   • Otherwise, do nothing (add \(0\))
4. Output total.

Complexity

• Time complexity: \(O(N)\) (each subject is processed once)
• Space complexity: \(O(1)\) (only a constant number of variables such as the running total)

Implementation Notes

• The total can be at most \((T-A_i)\le 10^4\), \(C_i\le 10^4\), \(N\le 10^5\), so the maximum value is around \(10^4 \times 10^4 \times 10^5 = 10^{13}\). Python’s int has arbitrary precision, so it is safe to use as-is.

• Since the input can be large, using sys.stdin.readline makes it faster.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    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)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.