#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
static char buf[1000000],*p1=buf,*p2=buf;
#define GC()	(p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)
#define PC(x)	putchar(x)
int read(){
	int x = 0; char c = GC();
	while(c < '0' || c > '9') c = GC();
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + c - '0'; c = GC();
	}
	return x;
}
lll Read(){
	lll x = 0; char c = GC();
	while(c < '0' || c > '9') c = GC();
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + c - '0'; c = GC();
	}
	return x;
}
void Write(lll x){
	if(x >= 10) Write(x / 10);
	PC(x % 10 + '0');
}
int Sub, n, m, k, tot, b[100010], ch[12000010][2];
ll sum[12000010];
lll N, ans, a[100010], mn[12000010];
bool chk(){
	int i;
	ll x = 0;
	lll y = N;
	for(i = 1; i <= n; i++) x += b[i], y = min(y, a[i]);
	if(x <= m){
		ans = y + N - 1;
		return true;
	}
	return false;
}
int add(){mn[++tot]=N;sum[tot]=ch[tot][0]=ch[tot][1]=0;return tot;}
void upd(lll x, int y){
	int i, j, u = 1;
	for(i = k - 1; 1; i--){
		mn[u] = min(mn[u], x);
		sum[u] += y;
		if(i < 0) break;
		j = x >> i & 1;
		if(ch[u][j] == 0) ch[u][j] = add();
		u = ch[u][j];
	}
}
void dfs(int o, int d, int m0, lll x, lll y, lll z){
	if(d < 0){ ans = max(ans, z); return; }
	lll u = ((lll)1 << d), v = u - 1;
	if(o <= 0){ ans = max(ans, y + (x | u | v)); return; }
	int lc = ch[o][0], rc = ch[o][1];
	bool fl = false;
	if(sum[lc] <= m0 && x + min(y, mn[lc]) > z){
		dfs(rc, d - 1, m0 - sum[lc], x, min(y, mn[lc]), z | u); fl = true;
	}
	if(sum[rc] <= m0 && (x | u) + min(y, mn[rc]) > z){
		dfs(lc, d - 1, m0 - sum[rc], x | u, min(y, mn[rc]), z | u); fl = true;
	}
	if(!fl){
		dfs(lc, d - 1, m0, x, y, z);
		dfs(rc, d - 1, m0, x | u, y, z);
	}
}
void solve(){
	ans = 0; tot = 0; add();
	int i;
	n = read(); m = read(); k = read();
	mn[0] = N = (lll)1 << k;
	for(i = 1; i <= n; i++){
		a[i] = Read();
	}
	for(i = 1; i <= n; i++){
		b[i] = read();
		upd(a[i], b[i]);
	}
	if(chk()){ Write(ans); PC('\n'); return; }
	dfs(1, k - 1, m, 0, N, 0);
	Write(ans); PC('\n');
}
int main()
{
	Sub = read();
	int t = read();
	while(t--) solve();
	return 0;
}