Overview

In this problem, we need to choose \(K\) problems from \(N\) candidate problems such that the sum of their point values is at least \(P\), while minimizing the maximum difficulty among the chosen problems. This can be solved by sorting the problems by difficulty and maintaining the “sum of the top \(K\) point values” using a priority queue (min-heap).

Analysis

Insight 1: “Minimizing the maximum” becomes easier by setting a threshold

Consider choosing \(K\) problems under the condition that “the maximum difficulty is at most \(X\).” Under this constraint, we can only use problems satisfying \(B_i \le X\). To maximize the total score when choosing \(K\) problems from these candidates, it is optimal to greedily pick the \(K\) problems with the largest point values \(A_i\).

That is, if we can determine:

Whether the sum of the top \(K\) largest \(A_i\) among the problems with \(B_i \le X\) is at least \(P\)

then we can know whether this \(X\) is a valid candidate for the answer.

Insight 2: The answer is always equal to some \(B_i\)

Since we are finding the minimum possible maximum value, the answer will be the difficulty of the most difficult problem actually chosen—which must be one of the \(B_i\) appearing in the input. Therefore, it suffices to only test \(B_1, \dots, B_N\) as values for \(X\).

Insight 3: Monotonicity allows binary search

Increasing \(X\) only adds more available problems, so the “sum of the top \(K\) point values” is monotonically non-decreasing. Thus, monotonicity holds with respect to the answer, and we can binary search on \(X\). However, sorting candidates again for each check would take around \(O(N \log^2 N)\), which is slightly inefficient.

Issues with Naive Approaches

• Try all combinations of \(K\) problems: There are \(\binom{N}{K}\) combinations (exponential), which is hopeless for \(N \le 10^5\).
• Use each \(B_i\) as a threshold and re-sort / re-calculate the top \(K\) each time: Each check takes \(O(N \log N)\), leading to \(O(N^2 \log N)\) overall, which results in TLE.

Solution: Process in ascending order of difficulty and maintain top \(K\) with a heap

We sort the problems in ascending order of \(B\) and add them to the “available set” one by one. You can think of this as gradually expanding the threshold starting from the smallest \(B\). At each step, we can update:

• The sum \(s\) of the top \(K\) values of \(A\) among the problems seen so far

in \(O(\log K)\) time using a min-heap (of size \(K\), containing the currently chosen values of \(A\)). The difficulty \(B\) at the very moment \(s \ge P\) is satisfied is the answer (increasing \(B\) further would only increase the maximum difficulty, so the first time the condition is met yields the minimum).

Algorithm

1. Form pairs \((B_i, A_i)\) and sort them in ascending order of \(B\).
2. Initialize an empty min-heap heap and the sum \(s = 0\).
3. Iterate through \((b, a)\) in sorted order:
   • If the size of the heap is less than \(K\), push \(a\) into the heap and update \(s \mathrel{+}= a\).
     • If the size reaches \(K\) and \(s \ge P\), the answer is \(b\); terminate.
   • If the size is \(K\): if \(a\) is strictly greater than the heap’s minimum element heap[0], discard the minimum and insert \(a\) (heappushpop). Update \(s\) by the difference.
     • If \(s \ge P\), the answer is \(b\); terminate.
   • If \(a \le\) heap[0], do nothing because replacing an element with \(a\) would only decrease or maintain the sum (and since merely making this problem available does not affect the answer, it can safely be ignored).
4. If \(s \ge P\) is never satisfied after examining all problems, output \(-1\).

Concrete Example

Let \(N = 4, K = 2, P = 10\), and \((A, B) = (3, 1), (8, 5), (6, 3), (2, 2)\).

Sorting in ascending order of \(B\) gives \((B, A) = (1, 3), (2, 2), (3, 6), (5, 8)\).

Step	Heap (Top 2 of \(A\))	\(s\)	Check
\((1,3)\)	\(\{3\}\)	3	Size \(<K\)
\((2,2)\)	\(\{2,3\}\)	5	\(5 < 10\)
\((3,6)\)	\(\{3,6\}\) (discard 2)	9	\(9 < 10\)
\((5,8)\)	\(\{6,8\}\) (discard 3)	14	\(14 \ge 10\) → Answer is \(5\)

The answer is \(5\).

Complexity

• Time complexity: \(O(N \log N)\) (Sorting takes \(O(N \log N)\), and heap operations take \(O(N \log K)\) in total)
• Space complexity: \(O(N)\) (To store the input; the heap itself takes \(O(K)\))

Implementation Notes

• Sort key order: If you store tuples as \((B_i, A_i)\), simply sorting them will naturally order them by ascending \(B\) (in the code, items is constructed in (B, A) order).

• Timing of returning the answer: After the heap size reaches \(K\), check \(s \ge P\) every time \(s\) is updated. You must not check when the size is less than \(K\), as \(K\) problems have not yet been chosen (in the code, this check is only performed once size \(K\) is reached via len(heap) == k and s >= p).

• When multiple problems have the same \(B\): Since we process in ascending order of \(B\), even if the condition is satisfied partway through processing problems with identical \(B\), that \(B\) is the correct answer and causes no issues.

• Update the sum by difference: Using the value old popped out by heappushpop, you can maintain the sum in \(O(1)\) via s += a - old. Summing all elements in the heap each time takes \(O(K)\) and risks getting TLE.

• Skipping when \(a \le\) heap[0]: If you forget this condition and call heappushpop unconditionally, the sum will decrease, resulting in WA.

• Overflow: With \(P \le 10^{14}\) and \(A_i \le 10^9\), the total sum can reach up to around \(10^{14}\). This is not an issue in Python due to arbitrary-precision integers, but in C++, long long must be used.

• Fast I/O: Since \(N \le 10^5\), reading all input at once with sys.stdin.buffer.read() is recommended for safety.

  Source Code

import sys, heapq

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1]); p = int(data[2])
    items = [(int(data[3 + 2*i + 1]), int(data[3 + 2*i])) for i in range(n)]
    items.sort()
    heap = []
    push = heapq.heappush
    pushpop = heapq.heappushpop
    s = 0
    for i in range(n):
        b, a = items[i]
        if len(heap) < k:
            push(heap, a)
            s += a
            if len(heap) == k and s >= p:
                print(b)
                return
        else:
            if a > heap[0]:
                old = pushpop(heap, a)
                s += a - old
                if s >= p:
                    print(b)
                    return
    print(-1)

main()

---

This editorial was generated by claude5opus-high.