【題解】Codeforces 1282B2. K for the Price of One (Hard Version)

#include <iostream>
#include <algorithm>
using namespace std;
 
const int maxn = 2e5+5;
int t, n, p, k, a[maxn], dp[maxn];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--){
        cin >> n >> p >> k;
        for (int i = 1; i <= n; i++){
            cin >> a[i];
        }
        sort(a+1, a+n+1);
        for (int i = 1; i < k; i++){
            dp[i] = dp[i-1] + a[i];
        }
        for (int i = k; i <= n; i++){
            dp[i] = dp[i-k] + a[i];
        }
        for (int i = n; i >= 0; i--){
            if (dp[i] <= p){
                cout << i << "\n";
                break;
            }
        }
    }
}