给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个整数 $$$k$$$。您还将获得一个长度为 $$$n$$$ 的二进制数组 $$$b$$$。
您最多可以执行以下操作 $$$k$$$ 次:
- 选择索引 $$$i$$$ ($$$1 \leq i \leq n$$$) 使得 $$$b_i = 1$$$。设置 $$$a_i = a_i + 1$$$ (即将 $$$a_i$$$ 增加 $$$1$$$)。
你的分数定义为 $$$\max\limits_{i = 1}^{n} \left( a_i + \operatorname{median}(c_i) \right)$$$,其中 $$$c_i$$$ 表示从 $$$a$$$ 中删除 $$$a_i$$$ 得到的长度为 $$$n-1$$$ 的数组。换句话说,您的分数是从 $$$1$$$ 到 $$$n$$$ 的所有 $$$i$$$ 中 $$$a_i + \operatorname{median}(c_i)$$$ 的最大值。
找出如果您以最佳方式执行操作,您可以获得的最高分数。
对于任意数组 $$$p$$$,$$$\operatorname{median}(p)$$$ 被定义为 $$$\left\lfloor \frac{|p|+1}{2} \right\rfloor$$$ - $$$p$$$ 的第一个最小元素。例如,$$$\operatorname{median} \left( [3,2,1,3] \right) = 2$$$ 和 $$$\operatorname{median} \left( [6,2,4,5,1] \right) = 4$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例都以两个整数 $$$n$$$ 和 $$$k$$$ 开头 ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq 10^9$$$) - $$$a$$$ 的长度和可以执行的操作数。
以下行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 表示数组 $$$a$$$。
以下行包含 $$$n$$$ 空格分隔的整数 $$$b_1、b_2、\ldots、b_n$$$($$$b_i$$$ 是 $$$0$$$ 或 $$$1$$$)— 表示数组 $$$b$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在新行中输出可以获得的最大值。
示例
输入 #1
8 2 10 3 3 1 1 3 10 3 3 3 0 0 0 4 4 2 1 5 1 0 1 0 1 5 4 7 5 2 5 4 0 0 1 0 1 5 1 5 15 15 2 11 1 0 0 1 1 5 2 10 11 4 10 15 1 1 0 1 0 4 4 1 1 2 5 1 1 0 0 2 1000000000 1000000000 1000000000 1 1
输出 #1
16 6 8 13 21 26 8 3000000000
注意
对于第一个测试用例,最好对两个元素执行 $$$5$$$ 操作,因此 $$$a = [8,8]$$$。因此,我们可以获得的最大分数是 $$$\max(8 + \operatorname{median}[8], 8 + \operatorname{median}[8]) = 16$$$,因为 $$$c_1 = [a_2] = [8]$$$。可以证明你不可能得到更好的分数。
对于第二个测试用例,您无法对任何元素执行操作,因此 $$$a$$$ 仍为 $$$[3,3,3]$$$。因此,我们可以获得的最大分数是 $$$3 + \operatorname{median}[3, 3] = 6$$$,即 $$$c_1 = [a_2, a_3] = [3, 3]$$$。可以证明你不可能得到更好的分数。