我们可以想到，答案在大部分情况下都是 $k$ 位的（注意，这里和下文中的位指二进制位），为什么是大部分情况呢？因为只要我们有一个水晶不是定向加强，那么这个水晶的魔力值 $a_i\oplus x$ 则一定不会超过 $k$ 位，因为 $a_i<2^k$，$x<2^k$。

那么小部分情况则是 $\sum_{i=1}^n b_i\le m$，所有水晶都可以定向加强，贪心地取 $x=2^k-1$，答案就是 $\min_{i\in U}(a_i + x)$，这时答案就是 $k+1$ 位的了（$a_i$ 最小值是 $0$ 除外）。

所以特判这种情况。

首先考虑只能异或的情况。

这就是一个典型的贪心问题。

考虑构建一颗字典树，然后贪心地从高到低考虑（设最高位为 $k-1$，最低位为 $0$）。假设考虑到了第 $i$ 位，那么枚举 $x$ 在第 $i$ 位的取值，假设枚举这一位是 $1$，那么它的左子树（即这一位为 $0$ 的儿子）就不用走了，因为它们对答案的贡献为 $1$，不是最小值；我们只用走右子树（即这一位为 $1$ 的儿子），因为它们对答案的贡献为 $0$，是最小值。枚举这一位是 $0$ 同理。时间复杂度 $O(nk)$。

接着考虑加上加法怎么办。

发现加法有一个性质：$\min_{i\in S}(a_i+x)=\min_{i\in S}(a_i)+x$，所以我们只需要实时记录定向加强中 $a_i$ 的最小值 $\text{minn}=\min_{i\in S}(a_i)$ 即可。

考虑上面的情景，枚举 $x$ 在第 $i$ 位的取值。假设枚举这一位是 $1$，那么它的右子树对答案的贡献是 $0$，我们可以尝试将右子树全部定向加强（变成加法）。假如可以（右子树的花费小于等于当前剩余的体力值），又分为两种情况：

• 右子树变成加法后的 $\text{minn}+x$ 还是不能将这一位变得比左子树答案大。

  这种情况，说明加法的答案是最小值，可以更新答案为 $\text{minn}+x$。

• 右子树变成加法后的 $\text{minn}+x$ 能将这一位变得比左子树答案大。

  这种情况，说明左子树的答案是最小值，我们更新 $\text{minn}$ 后走左子树继续判断。

其上，为了考虑极端情况，我们设 $x$ 的未确定部分为 $1$，左子树答案未确定部分为 $0$。

如果右子树的花费大于当前剩余的体力值，那么就不可行，又分为两种情况：

• $\text{minn}+x$ 不能将这一位变得比右子树答案大（注意这里的 $\text{minn}$ 是没有更新右子树的）。

  这种情况，说明加法的答案是最小值，可以更新答案为 $\text{minn}+x$。

• $\text{minn}+x$ 能将这一位变得比右子树答案大。

  这种情况，说明右子树的答案是最小值，我们走右子树继续判断。

其上，枚举 $x$ 这一位是 $0$ 同理。

然后可能需要剪剪枝，如果答案的一个位上能够填 $1$ 了，我们就不需要考虑这一位上答案填 $0$ 的情况了。剪完之后就可以拿满分。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define i28 __int128
#define son(x, y) trie[x].son[y]
#define cost(x) trie[x].cost
#define mn(x) trie[x].mn
#define get(x, y) ((x & ((i28)1 << y)) != 0)
#define inf 1e18
const ll N = 1e5 * 120 + 10;


void read(i28 &x){
	// read a __int128 variable
	char c; bool f = 0;
	while(((c = getchar()) < '0' || c > '9') && c != '-');
	if(c == '-'){f = 1; c = getchar();}
	x = c - '0';
	while((c = getchar()) >= '0' && c <= '9')x = x * 10 + c - '0';
	if(f) x = -x;
}
void write(i28 x){
	// print a __int128 variable
	if(x < 0){putchar('-'); x = -x;}
	if(x > 9)write(x / 10);
	putchar(x % 10 + '0');
}

ll c, T, n, m, k;

i28 a[N], mx;
ll b[N];

struct node {
	ll son[2], cost;
	i28 mn;
	void init() {
		cost = 0;
		son[0] = 0;
		son[1] = 0;
		mn = (i28)1 << k;
	}
} trie[N];
ll cnt;


void insert(i28 x, ll y) {
	ll p = 1;
	cost(p) += y;
	mn(p) = min(mn(p), x);
	for(ll i = k - 1; i >= 0; i--) {
		if(!son(p, get(x, i))) {
			son(p, get(x, i)) = ++cnt;
			trie[cnt].init();
		}
		p = son(p, get(x, i));
		cost(p) += y;
		mn(p) = min(mn(p), x);
	}
}

void dfs(ll p, ll use, ll i, i28 x, i28 minn, i28 tot) {
	i28 bit = ((i28)1 << i), mask = bit - 1;
	i28 x0 = x, x1 = x0 | bit;
	i28 mxx0 = x | mask, mxx1 = mxx0 | bit | mask;
	i28 tot0 = tot, tot1 = tot | bit;
	
	if(i < 0) {
		mx = max(mx, tot);
		return;
	}
	
	if(!p)
		return;
	
	bool flag = 1;
	
	// x取0
	if(cost(son(p, 0)) <= use) {
		if(mxx0 + min(mn(son(p, 0)), minn) < tot1) {
			if(min(mn(son(p, 0)), minn) < ((i28)1 << k))
				mx = max(mx, min(mn(son(p, 0)), minn) + mxx0);
		} else {
			dfs(son(p, 1), use - cost(son(p, 0)), i - 1, x0, min(mn(son(p, 0)), minn), tot1), flag = 0;
		}
	}
	
	
	// x取1
	if(cost(son(p, 1)) <= use) {
		if(mxx1 + min(mn(son(p, 1)), minn) < tot1) {
			if(min(mn(son(p, 1)), minn) < ((i28)1 << k))
				mx = max(mx, min(mn(son(p, 1)), minn) + mxx1);
		} else {
			dfs(son(p, 0), use - cost(son(p, 1)), i - 1, x1, min(mn(son(p, 1)), minn), tot1), flag = 0;
		}
	}
		
	if(flag) {
		if(mxx0 + minn < tot0) {
			if(minn < ((i28)1 << k))
				mx = max(mx, minn + mxx0);
		} else {
			dfs(son(p, 0), use, i - 1, x0, minn, tot0);
		}
		
		if(mxx1 + minn < tot0) {
			if(minn < ((i28)1 << k))
				mx = max(mx, minn + mxx1);
		} else {
			dfs(son(p, 1), use, i - 1, x1, minn, tot0);
		}
	}
}

int main(){
	scanf("%lld %lld", &c, &T);
	while(T--) {
		scanf("%lld %lld %lld", &n, &m, &k);
		mx = 0, cnt = 1;
		trie[0].init(), trie[1].init();
		ll sumb = 0;
		i28 mna = (i28)1 << k;
		for(ll i = 1; i <= n; i++)
			read(a[i]), mna = min(mna, a[i]);
		for(ll i = 1; i <= n; i++)
			scanf("%lld", &b[i]), sumb += b[i];
		if(sumb <= m)
			mx = ((i28)1 << k) - 1 + mna;
		for(ll i = 1; i <= n; i++)
			insert(a[i], b[i]);
		dfs(1, m, k - 1, 0, (i28)1 << k, 0);
		write(mx);
		putchar('\n');
	}
	return 0;
}