题目背景

我看到 satyam343 了。我浑身发抖。这次请多出一些中位数问题。我喜欢这些。satyam343，我们相信你。

— satyam343 的头号粉丝

题目描述

你将获得一个长度为 $n$ 的数组 $a$ 和一个整数 $k$ 。您还将获得一个长度为 $n$ 的二进制数组 $b$。

你先选出一个索引 $i'$，删除 $a_{i'}$，然后最多可​​以执行以下操作之一 $k$ 次：

• 选择一个索引 $i(1\le i\le n,i\ne i')$，满足 $b_i=1$。设置 $a_i=a_i+1$ (即，将 $a_i$ 增加 $1$)。
• 选择一个索引 $i(1\le i\le n,i\ne i')$，满足 $b_i=0$ 。设置 $a_i=a_i+1$ (即，将 $a_i$ 增加 $1$)。

你的得分定义为 $\oplus_{i=1}^n(a_i+\max\{\text{median}(c_i)\})$ ，其中 $c_i$ 表示从 $a$ 中删除 $a_i$ 后得到的长度为 $n−1$ 的数组。

对于任意数组 $p$， $\text{median}(p)$ 定义为 $p$ 中第 $⌊\frac{|p|+1}{2}⌋$ 个最小元素。例如， $\text{median}([3,2,1,3])=2$ 和 $\text{median}([6,2,4,5,1])=4$。

输入格式

第一行包含一个整数 $t(1\le t\le 10^4)$ — 测试用例的数量。

每个测试用例以两个整数 $n$ 和 $k(2\le n\le 2\cdot 10^5,0\le k\le 10^9)$ — 表示 $a$ 的长度和可以执行的操作数。

下一行包含 $n$ 个空格分隔的整数 $a_1,a_2,…,a_n(1\le a_i\le 10^9)$ — 表示数组 $a$。

以下行包含 $n$ 个空格分隔的整数 $b_1,b_2,…,b_n(b_i$ 为 $0$ 或 $1$ $)$ —— 表示数组 $b$。

保证所有测试用例的 $n$ 的总和不超过 $2\cdot 10^5$ 。

输出格式

对于每个测试用例，在新行上输出n可以获得的分数值。

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
12
21
26
8
3000000000