你喜欢鱼,这就是你决定建造一个水族馆的原因。您有一块由 $$$n$$$ 柱组成的珊瑚,其中第 $$$i$$$ 的高度为 $$$a_i$$$ 个单位。然后,您将在珊瑚周围建造一个水箱,如下所示:
- 选择一个整数 $$$h \geq 1$$$ — 水箱的高度。在水箱两侧建造高度 $$$h$$$ 的墙。
- 然后,将水箱注满水,使每根柱子的高度为$$$h$$$,除非珊瑚高于$$$h$$$;那么不应向该柱中添加水。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个正整数 $$$n$$$ 和 $$$x$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq x \leq 10^9$$$) — 珊瑚的列数和您可以使用的最大水量。
每个测试用例的第二行包含 $$$n$$$ 以空格分隔的整数 $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — 珊瑚的高度。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个正整数 $$$h$$$ ($$$h \geq 1$$$) - 水箱可以具有的最大高度,因此您最多需要 $$$x$$$ 单位的水来填满水箱。
我们有证据表明,在这些约束下,$$$h$$$ 这样的值总是存在。
示例
输入 #1
5 7 9 3 1 2 4 6 2 5 3 10 1 1 1 4 1 1 4 3 4 6 1984 2 6 5 9 1 8 1 1000000000 1
输出 #1
4 4 2 335 1000000001
注意
第一个测试用例如声明中所示。当 $$$h=4$$$ 时,我们需要 $$$8$$$ 单位的水,但如果 $$$h$$$ 增加到 $$$5$$$,我们需要 $$$13$$$ 单位的水,这比 $$$x=9$$$ 多。所以 $$$h=4$$$ 是最优的。
在第二个测试用例中,我们可以选择 $$$h=4$$$ 并向每列添加 $$$3$$$ 单位,总共使用 $$$9$$$ 单位的水。可以证明这是最优的。
在第三个测试用例中,我们可以选择 $$$h=2$$$ 并使用所有的水,因此这是最佳的。