#P1998C. Perform Operations to Maximize Score
Perform Operations to Maximize Score
Description
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$.
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$.
For each test case, output the maximum value of score you can get on a new line.
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.
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
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.