Overview

Given \(N\) subjects, this problem asks you to find the total study time required to bring all scores up to at least the passing score \(T\). For each subject \(i\), study time is calculated only when the score falls short of \(T\), to make up for the deficit.

Analysis

The key point for solving this problem is that “each subject is independent.” Since raising the score in one subject does not affect the scores of other subjects, we can calculate the “minimum time needed to reach the passing score” for each subject individually, and sum them all up to obtain the overall minimum time.

Specifically, let’s consider the study time needed for subject \(i\): - If the current score \(A_i\) is at least the passing score \(T\) (\(A_i \geq T\)) The passing score is already met, so the additional study time is \(0\). - If the current score \(A_i\) is below the passing score \(T\) (\(A_i < T\)) To reach the passing score, \(T - A_i\) more points are needed. Since it takes \(C_i\) hours to raise the score by \(1\) point, the study time needed for this subject is \((T - A_i) \times C_i\).

For example, if \(T=80, A_i=75, C_i=10\), then \(5 \times 10 = 50\) hours are needed to make up the missing \(5\) points.

Algorithm

The computation is performed using the following steps:

1. Initialize a variable total_study_time to \(0\) to hold the total study time.
2. For each subject \(i = 1, 2, \dots, N\), repeat the following:
   • If \(A_i < T\), add \((T - A_i) \times C_i\) to total_study_time.
   • Otherwise (if the passing score is already met), do nothing.
3. Output the final value of total_study_time.

Complexity

• Time complexity: \(O(N)\) Since we loop through each of the \(N\) subjects once to perform the computation, the processing completes in time proportional to the input size. Even for \(N = 10^5\), this runs sufficiently fast on modern computers.
• Space complexity: \(O(N)\) In this implementation, we use sys.stdin.read().split() to read all input at once as a list, so the memory usage is proportional to the amount of input data.

Implementation Notes

• Handling large numbers: The total study time in the answer can be as large as approximately \(10^5 \times 10^4 \times 10^4 = 10^{13}\). In Python, there is no limit on integer size, so this is not an issue. However, when using other languages (such as C++), you need to use a 64-bit integer type (such as long long) instead of a 32-bit integer type (int).

• Fast I/O: Since \(N\) can be as large as \(10^5\), reading all input at once using sys.stdin.read().split() can reduce execution time compared to calling input() for each subject.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 科目数 N と合格点 T を取得します
    N = int(input_data[0])
    T = int(input_data[1])
    
    total_study_time = 0
    
    # 各科目の得点 A_i と勉強時間 C_i を処理します
    for i in range(N):
        # A_i は input_data の 2 + 2*i 番目、C_i は 3 + 2*i 番目にあります
        a = int(input_data[2 + 2 * i])
        c = int(input_data[3 + 2 * i])
        
        # 得点が合格点 T 未満の場合、必要な勉強時間を加算します
        if a < T:
            needed_points = T - a
            total_study_time += needed_points * c
            
    # 合計勉強時間を出力します
    print(total_study_time)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.