Overview

For books that have been read \(K\) times or fewer, find the sum of their satisfaction values.

Analysis

In this problem, for each book we are given “the number of times read \(C_i\)” and “the satisfaction value \(D_i\)”. Takahashi considers only books that have been read \(K\) times or fewer as candidates for re-reading, and wants to know the total satisfaction of those books.

A straightforward approach is to check whether \(C_i \leq K\) for every book, and sum up \(D_i\) for those that satisfy the condition. This method does not require any complex processing and can obtain the answer in a single pass.

Looking at the constraints, \(N\) is at most \(2 \times 10^5\), so examining each element once is sufficiently fast. Also, since the answer is guaranteed to be at most \(2 \times 10^{14}\), it fits within the range of a 64-bit integer type.

Therefore, no special algorithms or data structures are needed — a simple brute-force scan suffices.

Algorithm

1. Read \(N\) and \(K\) from the input.
2. Initialize a variable total_satisfaction to \(0\) to hold the sum of satisfaction values.
3. For each book, do the following:
   • Read \(C_i\) and \(D_i\) from the input.
   • If \(C_i \leq K\), add \(D_i\) to total_satisfaction.
4. Output the final value of total_satisfaction.

With this method, we add up only the satisfaction values of books that meet the condition, obtaining the desired total.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Since we perform a constant-time operation for each book, the overall processing completes in time proportional to \(N\). Also, since the memory used aside from the input is of constant size, the space complexity is \(O(1)\).

Implementation Notes

• In the conditional branch if C <= K:, make sure that the boundary value (e.g., \(C = K\)) is included.

• The total satisfaction can be as large as \(2 \times 10^{14}\), so while this is not an issue in languages like Python, in C++ and similar languages you need to use a large integer type such as long long.

  Source Code

# 入力の受け取り
N, K = map(int, input().split())
total_satisfaction = 0

# 各本について処理
for _ in range(N):
    C, D = map(int, input().split())
    if C <= K:
        total_satisfaction += D

# 結果の出力
print(total_satisfaction)

This editorial was generated by qwen3-coder-480b.