Overview

Given \(N\) books, the problem asks us to select all books whose number of times read \(C_i\) is at most a specified upper limit \(K\), and compute the sum of their satisfaction values \(D_i\).

Analysis

What this problem requires is the very simple operation of “extracting elements that satisfy a condition and computing their sum.”

1. Condition check: For each book, determine whether “the number of times read \(C_i\) is at most \(K\) (\(C_i \leq K\)).”
2. Sum calculation: Only when the condition is satisfied, add that book’s satisfaction value \(D_i\) to the running total.
3. Constraint verification:
   • The number of books \(N\) is at most \(2 \times 10^5\). Checking each book one by one requires about \(2 \times 10^5\) computations in total, which is well within the time limit.
   • The number of times read \(C_i\) and the upper limit \(K\) can be as large as \(10^9\), but since they are only used for simple comparisons, the magnitude of these values does not affect computation speed.
   • The total satisfaction can reach up to \(2 \times 10^{14}\), but since Python’s integer type (int) can handle arbitrarily large values, there is no need to worry about overflow.

From the above, this problem can be solved with a “linear scan” approach that examines each piece of data exactly once.

Algorithm

1. Initialize a variable total_satisfaction to \(0\) to store the total satisfaction.
2. For each of the \(N\) books, repeat the following process:
   • Read the book’s data \((C_i, D_i)\).
   • If \(C_i \leq K\), add \(D_i\) to total_satisfaction.
3. Output the final value of total_satisfaction.

Complexity

• Time complexity: \(O(N)\)
  • Since each of the \(N\) books is checked exactly once, the processing time is proportional to \(N\).
• Space complexity: \(O(N)\)
  • In this implementation, sys.stdin.read().split() is used to read all input data into memory at once, so memory consumption is proportional to the input size.

Implementation Notes

• Fast I/O: In Python, when the number of inputs (\(N\)) is large, repeatedly calling input() can increase execution time. By using sys.stdin.read().split() to read all data at once and processing it with an iterator (map(int, ...)), data can be read efficiently.

• Conditional branching: There is a condition for “when no books match,” but by initializing the value to \(0\) and only adding when the condition is met, \(0\) is automatically output without needing any special handling.

  Source Code

import sys

def solve():
    # 標準入力から全てのデータを取得し、スペースや改行で分割する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # データを整数に変換するイテレータを作成
    it = map(int, input_data)
    
    # N（本の数）とK（読んだ回数の上限）を取得
    try:
        n = next(it)
        k = next(it)
    except StopIteration:
        return
    
    total_satisfaction = 0
    # 各本の「読んだ回数C」と「満足度D」を順に処理
    for _ in range(n):
        try:
            c = next(it)
            d = next(it)
            # 読んだ回数がK以下であれば満足度を加算
            if c <= k:
                total_satisfaction += d
        except StopIteration:
            break
            
    # 結果を出力
    print(total_satisfaction)

if __name__ == '__main__':
    solve()

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