Overview

This problem asks us to choose \(K\) problems out of \(N\) candidate problems such that the total score is at least \(P\), while minimizing the maximum difficulty among the chosen problems.

Analysis

Naive Approach and Its Challenges

A brute-force search trying all combinations (\(_N\mathrm{C}_K\) possibilities) requires an astronomical number of operations and will not run in time under the constraint \(N \le 10^5\).

Key Insight

Focus on the objective: “minimize the maximum difficulty as much as possible.” If we constrain the maximum difficulty of the chosen problems to at most \(X\), the sum of scores is maximized by picking the \(K\) problems with the largest scores \(A_i\) among those with difficulty at most \(X\). If this maximum sum is at least \(P\), it is possible to make the maximum difficulty at most \(X\).

While one could use binary search on the answer for this decision problem, we can solve it even more efficiently and simply by sorting the problems in ascending order of difficulty \(B_i\) and scanning through them.

We examine the problems one by one in increasing order of difficulty, constantly maintaining the \(K\) largest scores \(A_i\) among all problems seen so far. Because we process problems in increasing order of difficulty, the difficulty \(B_i\) at the exact moment the sum of the top \(K\) scores first becomes at least \(P\) is the desired minimum possible maximum difficulty.

Efficiently Maintaining the Top \(K\) Elements

To maintain the top \(K\) scores, we can use a min-heap (priority queue) of size \(K\). - When the number of elements in the heap is less than \(K\), we unconditionally add the score \(A_i\) to the heap. - When there are already \(K\) elements, we compare the top of the heap (the smallest score among the current top \(K\)) with the current score \(A_i\). If \(A_i\) is larger, we remove the minimum element and add \(A_i\).

This operation allows us to always maintain the “\(K\) largest scores seen so far” efficiently.

Algorithm

1. Store each problem as a pair \((\text{difficulty } B_i, \text{score } A_i)\) and sort them in ascending order of difficulty \(B_i\).
2. Prepare a min-heap h and a variable current_sum to store the sum of the scores currently in the heap.
3. Iterate through the sorted problems in order:
   • If len(h) < K: add \(A_i\) to h and add it to current_sum.
   • If len(h) == K and \(A_i > \text{minimum element of } h\): replace the minimum element of h with \(A_i\), and update current_sum with the difference.
   • If len(h) == K and current_sum >= P is satisfied, output the current \(B_i\) and terminate.
4. If all problems have been processed and the condition is never satisfied, it is impossible to make the sum of scores at least \(P\), so output -1.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Sorting the problems takes \(O(N \log N)\).
  • For each problem, we perform a heap operation (insertion or replacement), so the scanning phase takes \(O(N \log K)\).
  • Overall, the time complexity is \(O(N \log N + N \log K) = O(N \log N)\), which runs well within the time limit for the constraint \(N \le 10^5\).
• Space Complexity: \(O(N)\)
  • Storing the input list of problems takes \(O(N)\), and the heap size is at most \(K\) which takes \(O(K)\), resulting in \(O(N)\) overall.

Implementation Notes

• Using heapq.heapreplace: When the heap size is already \(K\), popping the minimum element and pushing the new value can be done simultaneously using heapq.heapreplace(h, a) for efficiency.

• Handling Integer Overflow: The target sum \(P\) and current_sum can reach up to around \(10^{14}\). While Python handles arbitrarily large integers automatically, when implementing in statically typed languages like C++, you must use a 64-bit integer type (long long).

  Source Code

import sys
import heapq

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    K = int(input_data[1])
    P = int(input_data[2])

    problems = []
    idx = 3
    for _ in range(N):
        a = int(input_data[idx])
        b = int(input_data[idx + 1])
        problems.append((b, a))
        idx += 2

    problems.sort(key=lambda x: x[0])

    h = []
    current_sum = 0

    for b, a in problems:
        if len(h) < K:
            heapq.heappush(h, a)
            current_sum += a
        elif h[0] < a:
            current_sum += a - h[0]
            heapq.heapreplace(h, a)

        if len(h) == K and current_sum >= P:
            print(b)
            return

    print(-1)

if __name__ == '__main__':
    main()

---

This editorial was generated by gemini-3.8-flash-high.