← 返回题目列表

Codeforces · 1282/B2

B2. K 一个的价格(硬版)

中文机器翻译题面 查看原题

这是这个问题的困难版本。唯一的区别是对 $$$k$$$ 的限制——优惠中的礼物数量。在此版本中:$$$2 \le k \le n$$$。

Vasya来到商店给朋友们采购新年物品。事实证明,他非常幸运——今天商店里有“一件商品$$$k$$$”的优惠。

使用此优惠,Vasya 可以精确购买 $$$k$$$ 的任何商品,只需支付其中最昂贵的商品。瓦夏决定趁这个机会,用自己的钱尽可能多地给朋友们买点东西。

更正式地说,对于每种商品,其价格由 $$$a_i$$$ 决定——其成本的硬币数量。最初,Vasya 拥有 $$$p$$$ 硬币。他想购买最大数量的商品。 Vasya 可以根据需要多次执行以下操作之一:

- 如果 Vasya 目前拥有足够的硬币(即 $$$p \ge a_i$$$),他可以购买索引为 $$$i$$$ 的商品。购买此商品后,Vasya 的金币数量将减少 $$$a_i$$$(即变为 $$$p := p - a_i$$$)。
- Vasya 可以购买指数为 $$$i$$$ 的商品,并且还可以精确选择 $$$k-1$$$ 商品,其价格不超过 $$$a_i$$$,如果他当前有足够的硬币(即 $$$p \ge 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$$$,而Vasya有$$$6$$$金币,那么他可以购买$$$3$$$商品。 Vasya 将在不使用优惠的情况下购买索引为 $$$1$$$ 的商品,并且他将支付 $$$2$$$ 硬币。指数为 $$$2$$$ 和 $$$3$$$ 的商品 Vasya 将使用该优惠购买,并且他将支付 $$$4$$$ 硬币。可以证明,瓦夏不能用六枚硬币购买更多的商品。

帮助 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 可以购买的最大商品数量。

示例

输入 #1

8
5 6 2
2 4 3 5 7
5 11 2
2 4 3 5 7
3 2 3
4 2 6
5 2 3
10 1 3 9 2
2 10000 2
10000 10000
2 9999 2
10000 10000
4 6 4
3 2 3 2
5 5 3
1 2 2 1 2

输出 #1

3
4
1
1
2
0
4
5