有一台自动售货机,卖柠檬水。该机器共有 $$$n$$$ 个插槽。您知道最初第 $$$i$$$ 个槽包含 $$$a_i$$$ 罐柠檬水。机器上还有$$$n$$$按钮,每个按钮对应一个槽位,每个槽位正好对应一个按钮。不幸的是,按钮上的标签已经磨损,因此您不知道哪个按钮对应哪个插槽。
当您按下与第 $$$i$$$ 个插槽对应的按钮时,会发生以下两个事件之一:
- 如果第 $$$i$$$ 槽中有一罐柠檬水,它会掉出来,你会拿走它。此时,第$$$i$$$槽中的罐子数量减少了$$$1$$$。
- 如果第 $$$i$$$ 槽中没有剩余柠檬水罐,则不会掉落任何东西。
按下后,罐子掉落得如此之快,以至于无法追踪它是从哪个槽落下的。插槽中的内容是隐藏的,因此您无法看到每个插槽中还剩下多少罐。您唯一知道的是插槽中罐子的初始数量:$$$a_1、a_2、\ldots、a_n$$$。
确定保证您收到至少 $$$k$$$ 罐柠檬水所需的最少按钮按下次数。
请注意,您可以根据是否收到罐头来调整按下按钮期间的策略。保证机器中总共至少有 $$$k$$$ 罐柠檬水。换句话说,$$$k \leq a_1 + a_2 + \ldots + a_n$$$。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \leq k \leq 10^9$$$) - 机器中的槽数和所需的柠檬水罐数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 槽中罐子的数量。
保证 $$$k \leq a_1 + a_2 + \ldots + a_n$$$,这意味着机器中至少有 $$$k$$$ 罐柠檬水。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 保证您收到至少 $$$k$$$ 罐柠檬水所需的最少按钮按下次数。
示例
输入 #1
5 2 1 1 1 2 2 1 2 3 4 2 1 3 10 50 1 1 3 8 8 9 12 13 27 27 2 1000000000 1000000000 500000000
输出 #1
1 2 5 53 1000000000
注意
在第一个测试用例中,我们只需按第一个按钮即可收到一罐柠檬水。
在第二个测试用例中,我们可以按每个按钮一次并保证我们收到 $$$2$$$ 罐柠檬水。请注意,如果我们只是按一个按钮两次,我们可能不会幸运,并且该按钮可能对应于第一个槽,在这种情况下,按两次我们只会收到 $$$1$$$ 罐柠檬水。
在第三个测试用例中,最优策略之一如下:
按第一个按钮两次。第一次压榨后,肯定会掉出一罐柠檬水。然后有两个选择:
- 如果第二次按下后没有一罐柠檬水掉落,我们知道该按钮必须对应于第二个插槽,因为 $$$a_2 = 1$$$ 且 $$$a_1, a_3 > 1$$$。然后我们可以按第二个按钮两次,第三个按钮一次。由于 $$$a_1, a_3 \geq 2$$$,我们肯定会收到这三台压榨机的三罐柠檬水。因此,在按下 $$$5$$$ 后,我们将得到 $$$4$$$ 罐柠檬水。
- 如果按第二次后一罐柠檬水掉落,我们可以按一下第二个按钮,再按一下第三个按钮。每次按下后,我们一定会收到一罐柠檬水。因此,在按下 $$$4$$$ 后,我们将得到 $$$4$$$ 罐柠檬水。
可以证明,仅用 $$$4$$$ 压机不可能保证收到 $$$4$$$ 罐柠檬水,所以答案是 $$$5$$$。