#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 n,m,k;
__int128 brr[100005],ans;
int lay[12000005],tag[12000005],cur;
int adj[2][12000005];
long long subt[12000005];
__int128 mn[12000005];
void addnode(int x, __int128 v, int l, long long br){
	subt[x]+=br;
	mn[x]=min(mn[x],v);
	if(l==-1) return;
	assert(l>=0);
	int go=0;
	if(v&((__int128)1<<(__int128)l)) go=1;
	if(adj[go][x]==-1){
		cur++;
		adj[go][x]=cur;
		lay[cur]=lay[x]-1;
		tag[cur]=tag[x]+((__int128)go<<l);
		subt[cur]=0;
		mn[cur]=1e18;
	}
	addnode(adj[go][x],v,l-1,br);
}
void rec(int x, long long cst, __int128 atl, __int128 val, __int128 xo, int l){
	if(l==-1){
		ans=max(ans,val);
		return;
	}
	if(x==-1){
		if(atl+xo+((__int128)1<<l)-1>=val) rec(-1,cst,atl,val+((__int128)1<<l),xo+((__int128)1<<l),l-1);
		return;
	}
	bool can=false;
	long long buy=cst+(adj[0][x]!=-1?subt[adj[0][x]]:0);
	__int128 natl=atl,nxo=xo,nval=val+((__int128)1<<l);
	if(adj[0][x]!=-1) natl=min(natl,mn[adj[0][x]]);
	if(buy<=m&&natl+nxo+((__int128)1<<l)-1>=nval){
		can=true;
		rec(adj[1][x],buy,natl,nval,nxo,l-1);
	}
	
	buy=cst+(adj[1][x]!=-1?subt[adj[1][x]]:0);
	natl=atl,nxo=xo+((__int128)1<<l);
	if(adj[1][x]!=-1) natl=min(natl,mn[adj[1][x]]);
	if(buy<=m&&natl+nxo+((__int128)1<<l)-1>=nval){
		can=true;
		rec(adj[0][x],buy,natl,nval,nxo,l-1);
	}
	if(!can){
		nxo=xo;
		if(atl+nxo+((__int128)1<<l)-1>=val) rec(adj[0][x],cst,atl,val,nxo,l-1);
		nxo=xo+((__int128)1<<l);
		if(atl+nxo+((__int128)1<<l)-1>=val) rec(adj[1][x],cst,atl,val,nxo,l-1);
	}
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	__int128 st,t;
	read(st);
	read(t);
	memset(adj,-1,sizeof(adj));
	while(t--){
		read(n); read(m); read(k);
		cur=0;
		ans=0;
		lay[0]=k-1;
		tag[0]=0;
		__int128 arr[n],sm=0;
		for(int i=0; i<n; i++) read(arr[i]);
		for(int i=0; i<n; i++) read(brr[i]),sm+=brr[i];
		if(sm<=m){
			__int128 smol=arr[0],ad=((__int128)1<<k)-1;
			for(int i=0; i<n; i++){
				if(smol>arr[i]) smol=arr[i];
			}
			ans=smol+ad;
		}
		for(int i=0; i<n; i++) addnode(0,arr[i],k-1,brr[i]);
		rec(0,0,0,0,0,k-1);
		
		write(ans);
		puts("");
		
		for(int i=0; i<=cur; i++){
			adj[0][i]=adj[1][i]=-1;
			lay[i]=0;
			tag[i]=0;
			subt[i]=0; mn[i]=1e18;
		}
		for(int i=0; i<n; i++){
			arr[i]=0;
			brr[i]=0;
		}
	}
}