C. Perform Operations to Maximize Score
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
I see satyam343. I'm shaking. Please more median problems this time. I love those. Please satyam343 we believe in you.
— satyam343's biggest fan

You are given an array $$$a$$$ of length $$$n$$$ and an integer $$$k$$$. You are also given a binary array $$$b$$$ of length $$$n$$$.

You can perform the following operation at most $$$k$$$ times:

  • Select an index $$$i$$$ ($$$1 \leq i \leq n$$$) such that $$$b_i = 1$$$. Set $$$a_i = a_i + 1$$$ (i.e., increase $$$a_i$$$ by $$$1$$$).

Your score is defined to be $$$\max\limits_{i = 1}^{n} \left( a_i + \operatorname{median}(c_i) \right)$$$, where $$$c_i$$$ denotes the array of length $$$n-1$$$ that you get by deleting $$$a_i$$$ from $$$a$$$. In other words, your score is the maximum value of $$$a_i + \operatorname{median}(c_i)$$$ over all $$$i$$$ from $$$1$$$ to $$$n$$$.

Find the maximum score that you can achieve if you perform the operations optimally.

For an arbitrary array $$$p$$$, $$$\operatorname{median}(p)$$$ is defined as the $$$\left\lfloor \frac{|p|+1}{2} \right\rfloor$$$-th smallest element of $$$p$$$. For example, $$$\operatorname{median} \left( [3,2,1,3] \right) = 2$$$ and $$$\operatorname{median} \left( [6,2,4,5,1] \right) = 4$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

Each test case begins with two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq 10^9$$$) — the length of the $$$a$$$ and the number of operations you can perform.

The following line contains $$$n$$$ space separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — denoting the array $$$a$$$.

The following line contains $$$n$$$ space separated integers $$$b_1, b_2, \ldots, b_n$$$ ($$$b_i$$$ is $$$0$$$ or $$$1$$$) — denoting the array $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output the maximum value of score you can get on a new line.

Example
Input
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
Output
16
6
8
13
21
26
8
3000000000
Note

For the first test case, it is optimal to perform $$$5$$$ operations on both elements so $$$a = [8,8]$$$. So, the maximum score we can achieve is $$$\max(8 + \operatorname{median}[8], 8 + \operatorname{median}[8]) = 16$$$, as $$$c_1 = [a_2] = [8]$$$. It can be proven that you cannot get a better score.

For the second test case, you are not able to perform operations on any elements, so $$$a$$$ remains $$$[3,3,3]$$$. So, the maximum score we can achieve is $$$3 + \operatorname{median}[3, 3] = 6$$$, as $$$c_1 = [a_2, a_3] = [3, 3]$$$. It can be proven that you cannot get a better score.