对于选定的\(p_i\)的情况下，如何使得代价小？显然是按照\(b\)升序的方式。
因此我们可以考虑按照\(b\)进行排序。
考虑一种贪心的做法，我们枚举区间\([l,r]\)，这样区间的必选就是\(a_l,a_r, (b_r- b_l)\)，因此我们可以贪心的选择剩下\(a\)中的最小值。这样复杂度是\(O(n^3\log n)\)。
考虑优化，我们可以维护一个大根堆，当枚举\(l,r\)的过程中，当\(r\)发生变化时，把\(a_r\)加入到堆中，并维护堆的和\(sum\)，当\(sum\)过大时，我们只需贪心的删除堆顶元素即可。
好现在考虑一种情况，会不会出现把\(a_l,a_r\) 从堆中删除的情况？答案是会的，但是这种情况一定不是最优解。
为什么？我们分开考虑，如果把\(a_l\)删去了，记此时堆中下标最小是\(l'\)，则一定有\(b_r - b_{l'} \le b_r - b_l\)，则说明当前的区间\([l,r]\)不会比\([l',r]\)更优。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ui32 = unsigned int;
using pii = pair<int,int>;
void solve() {
int n, m;
cin >> n >> m;
vector<pii> message(n);
for(auto &[b,a] : message)
cin >> a >> b;
ranges::sort(message);
int res = 0;
for(int l = 0; l < n; l ++) {
int sum = 0;
priority_queue<int> heap;
for(int r = l; r < n; r ++) {
heap.push(message[r].second), sum += message[r].second;
while(not heap.empty() and sum > m - message[r].first + message[l].first)
sum -= heap.top(), heap.pop();
res = max(res, (i32)heap.size());
}
}
cout << res << "\n";
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int TC;
cin >> TC;
while(TC --)
solve();
return 0;
}