\(B\) の小さい方から \(K\) 個の総和が \(T\) より大きいときは、答えが \(K\) 未満になります。このとき、乗るべきアトラクションは \(B\) の小さい順で良いです。

答えが \(K\) 以上であるときを考えます。 乗るアトラクションを決め打ったとき、ファストパスを使うべきアトラクションは \(A_{i} - B_{i}\) の大きい順に \(K\) 個です。

アトラクションが \(A_{i} - B_{i}\) の大きい順に並んでいると仮定します。\(K\) 個以上乗るアトラクションを決めると、index が \(a\) 以上なら普通に乗り、 \(a\) 未満ならファストパスで乗るような、整数 \(a\) が存在します。このような \(a\) を決め打ちます。

すると、\(a\) 未満の乗り物から \(K\) 個乗ることになりますが、これは \(B\) の小さい順に乗れば良いです。 \(B_{i} (i < a)\) の小さい方から \(K\) 個の総和を \(S_{a}\) とします。\(S_{a}\) は priority_queue を用いて \(O(N \log(N))\) で求まります。

そうすると結局、\(a = K + 1, K + 2, \dots, N\) に対して以下の問題が解ければ良いです。

\(A_{a}, A_{a + 1}, \dots, A_{N}\) から総和が \(T - S_{a}\) より小さくなるように要素をいくつか選ぶとき、その要素の数の最大値を求めてください。

これは例えば \(A\) が昇順になるような index の列を求めておけば、 segment tree の max_right を用いて \(O(N\log(N))\) 解くことができます。

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()

#include <atcoder/segtree>

struct F{
    ll a = 0;
    ll c = 0;
};

F op(F l, F r){
    l.a += r.a;
    l.c += r.c;
    return l;
}

F e(){
    return F{};
}

ll target;
bool f(F x){
    return x.a <= target;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll N, K, T;
    cin >> N >> K >> T;
    vector<pair<ll, ll>> A(N);
    vector<ll> B(N);
    rep(i, 0, N) cin >> A[i].first >> A[i].second, B[i] = A[i].second;
    // A[i] の昇順に並べる
    sort(all(A));
    sort(all(B));
    B.resize(K);
    ll bsum = 0;
    for (auto x : B) bsum += x;
    // 答えが T 未満になるとき
    if (bsum > T){
        ll sum = 0;
        int ind = 0;
        while (sum + B[ind] <= T) sum += B[ind++];
        cout << ind << "\n";
        return;
    }
    vector<int> order(N);
    rep(i, 0, N) order[i] = i;
    // order は B[i] - A[i] の降順
    sort(all(order), [&](int l, int r) {
        return A[l].first - A[l].second > A[r].first - A[r].second;
    });
    ll ans = K;
    ll sum = 0;
    priority_queue<ll> pq;
    atcoder::segtree<F, op, e> seg(N);
    rep(i, 0, N) seg.set(i, {A[i].first, 1});
    auto op = [&](int ind) -> void {
        ind = order[ind];
        seg.set(ind, e());
        sum += A[ind].second;
        pq.push(A[ind].second);
        if ((int)pq.size() > K){
            sum -= pq.top();
            pq.pop();
        }
    };
    rep(i, 0, K) op(i);
    rep(i, K, N){
        target = T - sum;
        if (target > 0){
            int b = seg.max_right<f>(0);
            ans = max(ans, K + seg.prod(0, b).c);
        }
        op(i);
    }
    cout << ans << "\n";
}