Overview

While examining the problems in ascending order of difficulty, we maintain the \(K\) problems with the largest scores among those seen so far. The difficulty when the sum of these scores becomes at least \(P\) for the first time is the answer.

Analysis

Fixing an Upper Bound on Difficulty: Greedily Choose Problems with the Highest Scores

Suppose we restrict the difficulties of all chosen problems to be at most \(x\).

In this case, choosing the \(K\) problems with the largest scores among those with difficulty at most \(x\) maximizes the total score. Therefore, a valid selection exists if and only if both of the following conditions are met:

• There are at least \(K\) problems with difficulty at most \(x\).
• The sum of the \(K\) largest scores among them is at least \(P\).

As the upper bound on difficulty increases, the number of available problems increases; thus, once the condition is satisfied, it will remain satisfied for all larger upper bounds.

Therefore, we can sort the problems in ascending order of difficulty and increase the available problems by \(1\) at a time.

Efficiently Maintaining the Top \(K\) Elements

Examining all combinations of \(K\) problems will not run in time because the number of combinations is enormous. Moreover, sorting the scores every time a problem is added would take around \(O(N^2 \log N)\) in total, which is also too slow.

What we need is only the top \(K\) scores among the problems seen so far. We can maintain these using a min-heap. A min-heap is a data structure that allows us to quickly retrieve the minimum of the stored values.

Let \(m\) be the minimum value among the current top \(K\) scores, and \(a\) be the score of the newly examined problem. The update proceeds as follows:

• If \(a \leq m\), the top \(K\) elements remain unchanged.
• If \(a > m\), remove \(m\) and insert \(a\).

By also maintaining the sum of the scores, we can update it simply by adding \(a-m\) whenever a replacement occurs.

For example, if \(K=3\) and the maintained scores are \(4,7,10\), when a problem with score \(8\) is added, \(4\) is replaced by \(8\). The sum changes from \(21\) to \(25\).

Algorithm

1. Store each problem as a pair (difficulty, score) and sort them in ascending order of difficulty.
2. Build a min-heap from the scores of the first \(K\) problems, and let total be their sum.
3. If total is at least \(P\), output the difficulty of the \(K\)-th problem from the beginning and terminate.
4. Iterate through the remaining problems. Let \(b\) be the difficulty and \(a\) be the score of the current problem.
   • If \(a\) is less than or equal to the minimum value in the heap, do nothing.
   • If \(a\) is strictly greater than the minimum value in the heap, replace the minimum value with \(a\) and update total.
   • If the updated total is at least \(P\), output \(b\) and terminate.
5. If the condition is never satisfied after examining all problems, output \(-1\).

Explanation of Correctness

Initially, exactly \(K\) problems have been examined, so the heap contains the top \(K\) scores among them.

When adding a new problem, replacing the minimum only when the new score is strictly greater ensures that the following invariant is maintained: the heap always contains the top \(K\) scores among all problems seen so far. Therefore, total represents the maximum possible sum when choosing \(K\) problems from those seen so far.

Let \(b\) be the current difficulty when total becomes at least \(P\) for the first time. Since all problems seen up to this point have difficulty at most \(b\), we can satisfy the condition with the maximum difficulty being at most \(b\).

On the other hand, all problems with difficulty strictly less than \(b\) have already been examined. Using only those problems, either there were fewer than \(K\) problems available, or the sum of the \(K\) largest scores was strictly less than \(P\). Therefore, no value smaller than \(b\) can be the answer, making \(b\) the minimum.

If the condition is never satisfied even after checking all problems, the sum of the \(K\) largest scores across all problems is still insufficient, so the answer is \(-1\).

Complexity

• Time Complexity: \(O(N \log N)\)
  Sorting takes \(O(N \log N)\), and all heap operations take \(O(N \log K)\) in total.
• Space Complexity: \(O(N)\)
  \(O(N)\) space is used to store the list of problems, and \(O(K)\) space is used for the heap.

Implementation Notes

• Python’s heapq module implements a min-heap. The minimum value can be accessed via heap[0].

• heapq.heapreplace(heap, a) pops and returns the smallest element, then pushes \(a\). In code, this can be used to update the sum as total += a - popped_value.

• Since the sum does not change if no replacement occurs, checking the condition is only necessary right after initialization and right after a replacement.

• Problems with the same difficulty do not need to be grouped together and can be processed \(1\) by \(1\). Even if the condition is satisfied midway through problems with the same difficulty, the output difficulty will be the same.

• The sum of the scores can reach up to \(10^{14}\), so languages with fixed-width integers require 64-bit integers. Python handles arbitrarily large integers automatically.

  Source Code

import sys
import heapq


def main():
    input = sys.stdin.buffer.readline
    N, K, P = map(int, input().split())

    problems = []
    for _ in range(N):
        a, b = map(int, input().split())
        problems.append((b, a))
    problems.sort()

    heap = [problems[i][1] for i in range(K)]
    total = sum(heap)
    heapq.heapify(heap)

    if total >= P:
        print(problems[K - 1][0])
        return

    replace = heapq.heapreplace
    for i in range(K, N):
        b, a = problems[i]
        if a > heap[0]:
            total += a - replace(heap, a)
            if total >= P:
                print(b)
                return

    print(-1)


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-6-astra-medium.