Overview

This is a problem where we have \(N\) students, and for each student, we lend them the book with the highest fun value \(S_i\) among books whose difficulty \(R_i\) does not exceed their reading ability \(T_j\). We need to find the total fun value.

Analysis

First, let’s consider a naive approach. For each student, if we check all \(M\) books to find the one with “difficulty at most \(T_j\)” and “maximum fun value,” the computational complexity would be \(O(N \times M)\). Given the constraints of this problem where \(N, M \leq 2 \times 10^5\), this would require up to about \(4 \times 10^{10}\) operations, which would not fit within the time limit.

Therefore, we focus on an important property for solving this efficiently: “A student with higher reading ability can read all the books that a student with lower reading ability can read.”

What if we sort students in ascending order of reading ability and books in ascending order of difficulty? 1. Check all books that the student with the lowest reading ability can read, and record the maximum fun value among them. 2. When considering the next student with slightly higher reading ability, “the books that the previous student could read” remain as candidates. 3. In other words, we only need to check the newly added candidate books (books with difficulty higher than what the previous student could handle but within the current student’s reading ability) and update the running maximum.

By sorting both students and books in ascending order and processing them sequentially, we can determine the optimal book for every student by checking each book only once.

Algorithm

1. Sort:
   • Sort books in ascending order of difficulty \(R_i\).
   • Sort students in ascending order of reading ability \(T_j\).
2. Scan (two-pointer style processing):
   • Initialize a variable max_fun to \(0\) to hold the maximum fun value among books the current student can read.
   • Process the sorted students one by one, performing the following operations:
     • As long as there are unchecked books with difficulty at most the current student’s reading ability, keep updating max_fun with those books’ fun values.
     • The best score for this student is the current max_fun, so add it to the running total.
3. Output:
   • Output the total for all students.

Complexity

• Time Complexity: \(O(M \log M + N \log N)\)
  • Sorting the books takes \(O(M \log M)\) and sorting the students takes \(O(N \log N)\).
  • The subsequent scan processes each student and each book at most once, so it is \(O(N + M)\).
• Space Complexity: \(O(N + M)\)
  • Memory is needed to store the input data.

Implementation Notes

• Fast I/O: Since \(N, M\) can be large, in Python using sys.stdin.read().split() or similar methods to read all input at once can reduce execution time.

• Lending the same book to multiple students: As stated in the problem, “the same book can be lent to multiple students,” so once we find the “maximum value so far,” it can be directly applied to subsequent students with higher reading ability. There is no need to manage book inventory, so simply maintaining the running maximum is sufficient.

  Source Code

import sys

def solve():
    # Read all input at once for fast processing
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Use an iterator to consume the input data
    it = iter(input_data)
    
    # Number of students and books
    N = int(next(it))
    M = int(next(it))
    
    # Store books as (difficulty, fun) tuples
    # Input order for each book is fun S_i then difficulty R_i
    books = []
    for _ in range(M):
        s = int(next(it))
        r = int(next(it))
        books.append((r, s))
        
    # Store student reading levels T_j
    students = []
    for _ in range(N):
        students.append(int(next(it)))
        
    # Sort books by difficulty (ascending)
    # If difficulties are equal, it sorts by fun (ascending)
    books.sort()
    
    # Sort students by reading level (ascending)
    students.sort()
    
    total_fun_sum = 0
    max_fun_available = 0
    book_idx = 0
    
    # Iterate through students in increasing order of reading level
    for t in students:
        # Add all books that the current student is capable of reading
        # Since students are sorted, the set of readable books for the next student
        # will always be a superset of the current student's readable books.
        while book_idx < M and books[book_idx][0] <= t:
            # Keep track of the maximum fun value encountered so far
            if books[book_idx][1] > max_fun_available:
                max_fun_available = books[book_idx][1]
            book_idx += 1
        
        # Add the maximum possible fun for this student to the total
        total_fun_sum += max_fun_available
        
    # Output the result
    sys.stdout.write(str(total_fun_sum) + '\n')

if __name__ == '__main__':
    solve()

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