Overview

Given \(N\) books, select all books that have been read \(K\) times or fewer, and find the total satisfaction of those books.

Analysis

This problem is very straightforward: for each book, determine whether “the number of times it has been read is \(K\) or fewer,” and simply sum up the satisfaction values of the books that meet the condition.

Key Observations

• Each book can be evaluated independently (no information about other books is needed)
• We just need to check one by one whether the condition \(C_i \leq K\) is satisfied
• No sorting or complex data structures are required

Thinking Through a Concrete Example

For example, suppose \(N = 3\), \(K = 2\), and we have the following books: - Book 1: times read \(C_1 = 1\), satisfaction \(D_1 = 100\) - Book 2: times read \(C_2 = 3\), satisfaction \(D_2 = 200\) - Book 3: times read \(C_3 = 2\), satisfaction \(D_3 = 150\)

The books read \(K = 2\) times or fewer are Book 1 (1 time) and Book 3 (2 times). Therefore, the answer is \(100 + 150 = 250\).

Why This Simple Approach Is Sufficient

• Since \(N \leq 2 \times 10^5\), examining each book once is fast enough
• Each book’s evaluation can be done in constant time \(O(1)\)
• No special optimization is needed

Algorithm

1. Initialize a variable total to \(0\) to hold the sum of satisfaction values
2. For each of the \(N\) books, do the following:
   • Read the number of times read \(C_i\) and the satisfaction \(D_i\) for that book
   • If \(C_i \leq K\), add \(D_i\) to total
3. Output the final value of total

Complexity

• Time complexity: \(O(N)\)
  • For each of the \(N\) books, we perform one condition check and one addition
• Space complexity: \(O(1)\)
  • We only use a variable to hold the total, and there is no need to store all book information

Implementation Notes

• Watch out for overflow: The maximum satisfaction value is \(10^9\) and the maximum number of books is \(2 \times 10^5\), so the total can be up to approximately \(2 \times 10^{14}\). In Python, there is no need to worry about integer overflow, but in C++ and similar languages, you need to use the long long type.

• When no books match the condition: If the initial value is set to \(0\), then even if no books satisfy the condition, \(0\) will naturally be output.

• Memory efficiency: Instead of storing all book information in an array, we evaluate and accumulate immediately while reading input, keeping the space complexity at \(O(1)\).

  Source Code

N, K = map(int, input().split())
total = 0
for _ in range(N):
    C, D = map(int, input().split())
    if C <= K:
        total += D
print(total)

This editorial was generated by claude4.5opus.