记 \(d_i=P_i-C_i\)，表示用优惠劵能优惠的钱数。
最后会有一些牛用优惠劵买，有一些牛用原价买，那么用优惠劵买的牛的 \(d\) 一定大于用原价买的牛的 \(d\)，否则把这张优惠劵用来买原价的这头牛肯定更优。
所以把所有牛按 \(d\) 排序后，一定可以找到一个分界点 \(i\)，使得 \(i\) 之前的牛都只用优惠劵买，\(i + 1\) 及之后的牛都只用原价买，那么我们把 \(1\sim i\) 的牛前 \(k\) 小的优惠价格和 \(i+1\sim n\) 的牛的原价拿出来排序，一个一个取直到取到总价格超过 \(m\)。
然后你发现，分界点 \(i\) 右移的过程中，只有 \(i\) 和 \(i+1\) 的状态发生了切换，因此我们可以用一个数据结构来维护所有价格，支持插入删除以及查不超过 \(m\) 最多选几个，可以使用权值线段树然后线段树上二分，也可以像我一样离散化后树状数组上二分。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, k, tot, cnt[N], lsh[N], ans;
priority_queue<int> q;
LL m, sum[N];
struct node {
int c, p;
bool operator<(const node &B) {
return p - c > B.p - B.c;
}
}a[N];
int find(int x) {
return lower_bound(lsh + 1, lsh + 1 + tot, x) - lsh;
}
int lowbit(int x) {
return x & (-x);
}
void add(int x, int v) {
for(int i = x; i <= tot; i += lowbit(i))
cnt[i] += v, sum[i] += lsh[x] * v;
}
int qry() {
LL now = 0;
int pos = 0, res = 0;
for(int i = 18; i >= 0; i--)
if(pos + (1 << i) <= tot && now + sum[pos + (1 << i)] <= m)
pos += 1 << i, res += cnt[pos], now += sum[pos];
return res;
}
int main() {
cin>>n>>k>>m;
for(int i = 1; i <= n; i++) {
scanf("%d%d", &a[i].p, &a[i].c);
lsh[++tot] = a[i].c;
lsh[++tot] = a[i].p;
}
sort(a + 1, a + 1 + n);
sort(lsh + 1, lsh + 1 + tot), tot = unique(lsh + 1, lsh + 1 + tot) - lsh - 1;
for(int i = 1; i <= n; i++) add(find(a[i].p), 1);
for(int i = 0; i <= n; i++) {
ans = max(ans, qry());
if(i < n) {
add(find(a[i + 1].p), -1);
add(find(a[i + 1].c), 1);
q.push(a[i + 1].c);
if((int)q.size() > k) {
int val = q.top();
q.pop();
add(find(val), -1);
}
}
}
cout<<ans<<endl;
return 0;
}