「難易度が \(X\) 以下の問題だけを \(K\) 問選んで配点の合計を \(P\) 点以上にできるか？」という問題を考えます。 これは、使うことができる問題のうち配点が大きいほうから \(K\) 問を選び、配点の合計が \(P\) 以上になっているかを判定することで解くことができます。

これを利用して二分探索を行うことで \(O(N\log N)\) 時間などでこの問題を解くことができます。

また、「使うことができる問題のうち配点が大きいほうから \(K\) 問」を優先度付きキューなどを使って管理することで、新しく問題を追加して配点の合計を求める操作を \(O(\log K)\) 時間で行うことができます。 これを利用して難易度が小さいほうから問題を処理していくことで全体で \(O(N\log K)\) 時間で解くこともできます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int main() {
    int N, K;
    long P;
    cin >> N >> K >> P;

    vector<pair<int, int>> problems(N);
    for (auto& [A, B] : problems) {
        cin >> A >> B;
    }
    // 難易度の昇順に並べる
    ranges::sort(problems, {}, [](pair<int, int> p) { return p.second; });

    // これまで見た中で配点が大きいほうから K 個を管理する優先度付きキュー
    priority_queue<int, vector<int>, greater<>> pq;
    long sum = 0;
    for (auto [A, B] : problems) {
        pq.emplace(A);
        sum += A;
        if (size(pq) > K) { // K 個を上回ったら
            sum -= pq.top(); // 配点が小さいものを取り除く
            pq.pop();
        }
        // 合計が P 以上になったら
        if (size(pq) == K && sum >= P) {
            cout << B << endl; // その時点の難易度が答え
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

from heapq import heappush, heappop


N, K, P = map(int, input().split())

problems = [tuple(map(int, input().split())) for i in range(N)]
# 難易度の昇順に並べる
problems.sort(key=lambda p: p[1])

# これまで見た中で配点が大きいほうから K 個を管理する優先度付きキュー
pq = []
sum = 0

for A, B in problems:
    heappush(pq, A)
    sum += A

    if len(pq) > K: # K 個を上回ったら
        sum -= heappop(pq) # 配点が小さいものを取り除く

    # 合計が P 以上になったら
    if len(pq) == K and sum >= P:
        print(B) # その時点の難易度が答え
        break
else:
    print(-1)