#include<bits/stdc++.h>
using namespace std;
void read(__int128 &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(__int128 x){
	// print a __int128 variable
	if(x < 0){putchar('-'); x = -x;}
	if(x > 9)write(x / 10);
	putchar(x % 10 + '0');
}
__int128 a[100005];
int b[100005];
int ss[12000005][2],tot=1;
long long hb[12000005];
__int128 zx[12000005];
__int128 yihuo(int x,int t){
	if(t==-1)return 0;
	__int128 zb=(__int128)1<<t;
	if(!ss[x][0])return zb|yihuo(ss[x][1],t-1);
	if(!ss[x][1])return zb|yihuo(ss[x][0],t-1);
	return max(yihuo(ss[x][1],t-1),yihuo(ss[x][0],t-1));
}
__int128 suan(bool q,__int128 x,int y,int t){
	if(t==-1)return 0;
	int xq=(x>>t)&1;
	__int128 xh=x&(((__int128)1<<(t+1))-1);
	if(q){
		if(xq){
			__int128 ans=0;
			if(!ss[y][1]){
				ans=max(ans,suan(1,xh,ss[y][0],t-1)+((__int128)1<<(t+1)));
			}else{
				if(!ss[y][0]){
					ans=max(ans,xh+((__int128)1<<(t+1))-1);
				}else{
					ans=max(ans,suan(1,xh,ss[y][0],t-1)+((__int128)1<<t));
				}
				ans=max(ans,suan(0,xh,ss[y][1],t-1)+((__int128)1<<(t+1)));
			}
			return ans;
		}else{
			if(!ss[y][1]){
				return xh+((__int128)1<<(t+1))-1;
			}
			return suan(1,xh,ss[y][1],t-1)+((__int128)1<<t);
		}
	}
	if(xq){
		if(!ss[y][0]){
			return suan(0,xh,ss[y][1],t-1)+((__int128)1<<t);
		}
		if(!ss[y][1]){
			return yihuo(ss[y][0],t-1)+((__int128)1<<t);
		}
		__int128 ans=0;
		ans=max(ans,yihuo(ss[y][0],t-1));
		ans=max(ans,yihuo(ss[y][1],t-1));
		return ans;
	}else{
		if(!ss[y][0]){
			return xh+((__int128)1<<t)-1;
		}
		if(!ss[y][1]){
			return suan(0,xh,ss[y][0],t-1)+((__int128)1<<t);
		}
		__int128 ans=0;
		ans=max(ans,suan(0,xh,ss[y][0],t-1));
		ans=max(ans,yihuo(ss[y][1],t-1));
		return ans;
	}
	return 0;
}
__int128 dfs(int x,int m,int t,int fl=0){
	if(!t)return 1;
	if(!ss[x][0]){
		return dfs(ss[x][1],m,t-1,fl)+((__int128)1<<t);
	}
	if(!ss[x][1]){
		return dfs(ss[x][0],m,t-1,fl)+((__int128)1<<t);
	}
	__int128 ans=0;
	if(m<hb[ss[x][0]]&&m<hb[ss[x][1]]){
		ans=max(ans,dfs(ss[x][0],m,t-1,fl));
		ans=max(ans,dfs(ss[x][1],m,t-1,1));
	}
	if(m>=hb[ss[x][0]]){
		__int128 a=zx[ss[x][0]];
		if(!fl)ans=max(ans,suan(1,a,ss[x][1],t-1));
		else
		ans=max(ans,((__int128)1<<t)+dfs(ss[x][1],m-hb[ss[x][0]],t-1,fl));
	}
	if(m>=hb[ss[x][1]]){
		ans=max(ans,((__int128)1<<t)+dfs(ss[x][0],m-hb[ss[x][1]],t-1,fl));
	}
	return ans;
}
int main(){
	freopen("2.in","r",stdin);
	int c,T;
	scanf("%d%d",&c,&T);
	while(T--){
		int n,m,k;
		scanf("%d%d%d",&n,&m,&k);
		for(int i=1;i<=n;++i)read(a[i]);
		long long he=0;
		for(int i=1;i<=n;++i)scanf("%d",&b[i]),he+=b[i];
		if(he<=m){
			__int128 mx=a[1];
			for(int i=1;i<=n;++i)mx=min(mx,a[i]);
			__int128 ans=mx+((__int128)1<<k)-1;
			write(ans);putchar('\n');
			continue;
		}
		for(int i=1;i<=tot;++i){
			ss[i][0]=ss[i][1]=0;
			hb[i]=0;
		}
		tot=1;
		for(int i=1;i<=n;++i){
			int r=1;
			for(int j=k-1;j>=0;--j){
				int z=(a[i]>>j)&1;
				if(!ss[r][z])ss[r][z]=++tot,zx[tot]=a[i];
				r=ss[r][z];hb[r]+=b[i];zx[r]=min(zx[r],a[i]);
			}
		}
		write(dfs(1,m,k-1));putchar('\n');
	}
	return 0;
}