这是这个问题的简单版本。唯一的区别是对 $$$k$$$ 的限制——优惠中的礼物数量。在此版本中:$$$k=2$$$。
Vasya来到商店给朋友们采购新年物品。事实证明,他非常幸运——今天商店里有“一件商品$$$k$$$”的优惠。请记住,在这个问题中$$$k=2$$$。
使用此优惠,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$$$, $$$k=2$$$) – 商店中的商品数量,Vasya 拥有的硬币数量以及可以购买的商品数量其中最贵的价格。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \le a_i \le 10^4$$$) — 商品的价格。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。可以保证在这个版本的问题中,对于所有测试用例,$$$k=2$$$。
输出
对于单独行中的每个测试用例,打印一个整数 $$$m$$$ — Vasya 可以购买的最大商品数量。
示例
输入 #1
6 5 6 2 2 4 3 5 7 5 11 2 2 4 3 5 7 2 10000 2 10000 10000 2 9999 2 10000 10000 5 13 2 8 2 8 2 5 3 18 2 1 2 3
输出 #1
3 4 2 0 4 3