CF1282B2.K for the Price of One (Hard Version)

This is the hard version of this problem. The only difference is the constraint on $k$ — the number of gifts in the offer. In this version: $2 \le k \le n$.

Vasya came to the store to buy goods for his friends for the New Year. It turned out that he was very lucky — today the offer "$k$ of goods for the price of one" is held in store.

Using this offer, Vasya can buy exactly $k$ of any goods, paying only for the most expensive of them. Vasya decided to take this opportunity and buy as many goods as possible for his friends with the money he has.

More formally, for each good, its price is determined by $a_i$ — the number of coins it costs. Initially, Vasya has $p$ coins. He wants to buy the maximum number of goods. Vasya can perform one of the following operations as many times as necessary:

• Vasya can buy one good with the index $i$ if he currently has enough coins (i.e $p \ge a_i$). After buying this good, the number of Vasya's coins will decrease by $a_i$, (i.e it becomes $p := p - a_i$).
• Vasya can buy a good with the index $i$, and also choose exactly $k-1$ goods, the price of which does not exceed $a_i$, if he currently has enough coins (i.e $p \ge a_i$). Thus, he buys all these $k$ goods, and his number of coins decreases by $a_i$ (i.e it becomes $p := p - a_i$).

Please note that each good can be bought no more than once.

For example, if the store now has $n=5$ goods worth $a_1=2, a_2=4, a_3=3, a_4=5, a_5=7$, respectively, $k=2$, and Vasya has $6$ coins, then he can buy $3$ goods. A good with the index $1$ will be bought by Vasya without using the offer and he will pay $2$ coins. Goods with the indices $2$ and $3$ Vasya will buy using the offer and he will pay $4$ coins. It can be proved that Vasya can not buy more goods with six coins.

Help Vasya to find out the maximum number of goods he can buy.

这是本题的困难版本。唯一的区别在于对 $k$（优惠中商品的数量）的约束。在本版本中：$2 \le k \le n$。

瓦夏来到商店，为朋友们购买新年礼物。结果他非常幸运——今天商店正在举行“$k$ 件商品仅需支付其中最贵一件的价格”的优惠活动。

利用该优惠，瓦夏可以恰好购买任意 $k$ 件商品，但只需支付其中最贵的那一件的价格。瓦夏决定抓住这个机会，用自己所拥有的钱尽可能多地为朋友们购买商品。

更形式化地，每件商品 $i$ 的价格为 $a_i$（即花费 $a_i$ 枚硬币）。初始时，瓦夏有 $p$ 枚硬币。他希望购买尽可能多的商品。瓦夏可以无限次执行以下两种操作之一：

• 若当前硬币数足够（即 $p \ge a_i$），瓦夏可单独购买第 $i$ 件商品；购买后，他的硬币数减少 $a_i$（即变为 $p := p - a_i$）。
• 若当前硬币数足够（即 $p \ge a_i$），瓦夏可购买第 $i$ 件商品，并额外任选恰好 $k-1$ 件价格不超过 $a_i$ 的商品；于是他一次性购得这 $k$ 件商品，但仅需支付 $a_i$ 枚硬币（即硬币数变为 $p := p - a_i$）。

请注意：每件商品至多只能被购买一次。

例如，若商店当前有 $n=5$ 件商品，其价格分别为 $a_1=2,\, a_2=4,\, a_3=3,\, a_4=5,\, a_5=7$，$k=2$，且瓦夏有 $6$ 枚硬币，则他最多可购买 $3$ 件商品：第 $1$ 件商品单独购买，花费 $2$ 枚硬币；第 $2$ 和第 $3$ 件商品使用优惠一起购买，花费 $4$ 枚硬币（取二者中较贵者）。可以证明，在仅有 $6$ 枚硬币的情况下，瓦夏无法购买更多商品。

请帮助瓦夏计算他最多能购买多少件商品。

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

The next lines contain a description of $t$ test cases.

The first line of each test case contains three integers $n, p, k$ ($2 \le n \le 2 \cdot 10^5$, $1 \le p \le 2\cdot10^9$, $2 \le k \le n$) — the number of goods in the store, the number of coins Vasya has and the number of goods that can be bought by the price of the most expensive of them.

The second line of each test case contains $n$ integers $a_i$ ($1 \le a_i \le 10^4$) — the prices of goods.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

接下来的若干行描述了 $t$ 个测试用例。

每个测试用例的第一行包含三个整数 $n, p, k$（$2 \le n \le 2 \cdot 10^5$，$1 \le p \le 2\cdot10^9$，$2 \le k \le n$）—— 分别表示商店中商品的数量、Vasya 拥有的硬币数量，以及可以按其中最贵商品价格购买的商品数量。

每个测试用例的第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^4$）—— 各商品的价格。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case in a separate line print one integer $m$ — the maximum number of goods that Vasya can buy.

对于每个测试用例，在单独的一行中输出一个整数 $m$ —— Vasya 最多能购买的商品数量。