CF1282B2 K for the Price of One (Hard Version)

这是本题的困难版本。唯一的区别在于 $k$ ——即优惠中可购买的商品数量的约束。在本题中：$2 \le k \le n$。 Vasya 来到商店为朋友们购买新年礼物。结果他非常幸运——今天商店正在举行“$k$ 件商品只需支付最贵一件的价格”的优惠活动。 利用这个优惠，Vasya 可以任选 $k$ 件商品，只需支付其中最贵一件的价格。Vasya 决定抓住这个机会，用手头的钱为朋友们尽可能多地购买商品。 更正式地说，每件商品的价格由 $a_i$ 给出——即该商品的价格为 $a_i$ 个硬币。Vasya 最初有 $p$ 个硬币。他想要购买尽可能多的商品。Vasya 可以不限次数地进行以下两种操作之一： - 如果 Vasya 当前有足够的硬币（即 $p \ge a_i$），他可以单独购买编号为 $i$ 的一件商品。购买后，Vasya 的硬币数减少 $a_i$（即 $p := p - a_i$）。 - 如果 Vasya 当前有足够的硬币（即 $p \ge a_i$），他可以购买编号为 $i$ 的一件商品，并再选择恰好 $k-1$ 件价格不超过 $a_i$ 的商品。这样，他可以用 $a_i$ 个硬币买下这 $k$ 件商品（即 $p := p - a_i$）。 请注意，每件商品最多只能被购买一次。 例如，假设商店有 $n=5$ 件商品，价格分别为 $a_1=2, a_2=4, a_3=3, a_4=5, a_5=7$，$k=2$，Vasya 有 $6$ 个硬币。那么他最多可以购买 $3$ 件商品。Vasya 可以不使用优惠单独购买编号为 $1$ 的商品，花费 $2$ 个硬币。然后，他可以用优惠购买编号为 $2$ 和 $3$ 的商品，花费 $4$ 个硬币。可以证明，Vasya 用 $6$ 个硬币无法买到更多商品。 请你帮助 Vasya 计算他最多能买到多少件商品。

第一行包含一个整数 $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$。

对于每个测试用例，输出一行一个整数 $m$，表示 Vasya 最多能买到的商品数量。

由 ChatGPT 4.1 翻译