#pragma GCC optimize("O3")
#include <iostream>
#include <algorithm>
using namespace std;
const int mx=100000, mk=120;
typedef long long ll; typedef __int128 I;

void read(__int128 &x){
	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){
	if(x < 0){putchar('-'); x = -x;}
	if(x > 9)write(x / 10);
	putchar(x % 10 + '0');
}

I a[mx]; ll b[mx+1]; pair<I,ll> tmp[mx]; //b prefsums
int mid(int l, int r, int t)
{
    int L=l-1, R=r;
    while(R!=L+1) if((a[(L+R)/2]>>t)&1) R=(L+R)/2; else L=(L+R)/2;
    return R;
}
I f1(int,int,int,ll), F1[mk][mx];
I f2(int,int,int,ll), F2[mk][mx];
I f3(int,int,int,ll,I);
I f4(int,int,int,ll,I);
I f1(int l, int r, int t, ll M)
{
    if(t==-1) return 0;
if(F1[t][l]!=-1) return F1[t][l];
    if(b[r]-b[l]<=M) return F1[t][l]=a[l]+(I(1)<<(t+1))-1;
int m=mid(l,r,t); I sA=b[m]-b[l], sB=b[r]-b[m], ans=0; bool A=sA<=M, B=sB<=M;
    if(l==m) return F1[t][l]=f1(m,r,t-1,M)+(I(1)<<t);
    if(!A) ans=max(ans,f1(l,m,t-1,M));
    if(!B) ans=max(ans,f2(m,r,t-1,M));
    if(!A&&B) ans=max(ans,f1(l,m,t-1,M-sB)+(I(1)<<t));
    if(A&&!B) ans=max(ans,(I(1)<<t)-1);
    if(A&&!(a[l]&((I(1)<<t)-1)))
        ans=max(ans,f3(m,r,t-1,M-sA,
                       (I(1)<<t)-(a[l]&((I(1)<<t)-1)))+(I(1)<<t));
    if(A&&B) ans=max(ans,f1(l,m,t-1,M-sB))+(I(1)<<t);
    return F1[t][l]=ans;
}
I f2(int l, int r, int t, ll M)
{
    if(t==-1) return 0;
if(F2[t][l]!=-1) return F2[t][l];
int m=mid(l,r,t); I sA=b[m]-b[l], sB=b[r]-b[m], ans=0; bool A=sA<=M, B=sB<=M;
    if(!A) ans=max(ans,f2(l,m,t-1,M));
    if(!B) ans=max(ans,f2(m,r,t-1,M));
    if(!A&&B) ans=max(ans,f2(l,m,t-1,M-sB)+(I(1)<<t));
    if(A&&!B) ans=max(ans,f2(m,r,t-1,M-sA)+(I(1)<<t));
    return F2[t][l]=ans;
}
I f3(int l, int r, int t, ll M, I c)
{
    if(t==-1) return 0;
    if(l==r) return (I(1)<<t)-1-c;
int m=mid(l,r,t); I sA=b[m]-b[l], sB=b[r]-b[m], ans=0; bool A=sA<=M, B=sB<=M;
    if((c>>t)&1) return f3(m,r,t-1,M,c-(I(1)<<t));
    ans=max(ans,f3(l,m,t-1,M,c));
    ans=max(ans,f4(m,r,t-1,M,(I(1)<<t)-c));
    if(B) ans=max(ans,f4(l,m,t-1,M-sB,(I(1)<<t)-c)+(I(1)<<t));
    return ans;
}
I f4(int l, int r, int t, ll M, I c)
{
    if(t==-1) return 0;
    if(b[r]-b[l]<=M) return (I(1)<<(t+1))-1+c;
    if((c&((I(1)<<(t+1))-1))>=(a[l]&((I(1)<<(t+1))-1))) return f1(l,r,t,M);
int m=mid(l,r,t); I sA=b[m]-b[l], sB=b[r]-b[m], ans=0; bool A=sA<=M, B=sB<=M;
    if((c>>t)&1) return f4(m,r,t-1,M,c-(I(1)<<t))+(I(1)<<t);
    if(l==m) return f1(m,r,t-1,M)+(I(1)<<t);
    if(!A) ans=max(ans,f4(l,m,t-1,M,c));
    if(!B) ans=max(ans,f2(m,r,t-1,M));
    if(!A&&B) ans=max(ans,f4(l,m,t-1,M-sB,c)+(I(1)<<t));
    if(A&&!B) ans=max(ans,(I(1)<<t)-1);
    if(A&&!(c&((I(1)<<t)-1)))
        ans=max(ans,f3(m,r,t-1,M-sA,
                       (I(1)<<t)-(c&((I(1)<<t)-1)))+(I(1)<<t));
    if(A&&B) ans=max(ans,f4(l,m,t-1,M-sB,c)+(I(1)<<t));
    return ans;
}
I solve()
{
    int n, k; ll m; cin>>n>>m>>k;
    for(int i=0; i<k; i++) for(int j=0; j<n; j++) F1[i][j]=F2[i][j]=-1;
    for(int i=0; i<n; i++) read(tmp[i].first);
    for(int i=0; i<n; i++) cin>>tmp[i].second;
    sort(tmp,tmp+n);
    for(int i=0; i<n; i++) a[i]=tmp[i].first, b[i+1]=b[i]+tmp[i].second;
    return f1(0,n,k-1,m);
}
int main()
{
    int T; cin>>T>>T; while(T--) write(solve()), cout<<'\n';
}
/* [l,r) with max 2^(t+1)-1 and M
 * split into a_i (A_i) and b_i+2^t (B_i), 0 <= a_i,b_i < 2^t
 * A = [M >= sum A_i]
 * B = [M >= sum B_i]
 * X = [x >= 2^t]
 * C = [c >= 2^t]
 * . means empty, 1. means nonempty 1; .U1. = 1
 * A B X C
 * f1:
 * A+B      min+2^(t+1)-1
 * . 0 0    f1(b_i,M)+2^t
 * 0   0    f1(a_i,M)
 *   0 1    f2(b_i,M)
 * 0 1 1    f1(a_i,M-sB)+2^t
 * 1.0 0    2^t-1
 * 1.  0    f3(b_i,M-sA,2^t-a_0)+2^t if a_0 > 0
 * 1.1 1    f1(a_i,M-sB)+2^t
 * f2: add=del
 * 0   0    f2(a_i,M)
 *   0 1    f2(b_i,M)
 * 0 1 1    f2(a_i,M-sB)+2^t
 * 1 0 0    f2(b_i,M-sA)+2^t
 * f3: x-c term, 0 <= c < 2^(t+1)
 * . .      2^t-1-c
 *     1 1  f3(b_i,M,c-2^t)
 *       0
 *     0    f3(a_i,M,c)
 *     1    f4(b_i,M,2^t-c)
 *   1 1    f4(a_i,M-sB,2^t-c)+2^t
 * f4: x+c term, 0 <= c <= 2^(t+1)
 * A+B      2^(t+1)-1+c
 * c>=min   f1(same,M)
 * . 0 0 1  f4(b_i,M,c-2^t)+2^t
 *       0
 * . 0 0    f1(b_i,M)+2^t
 * 0   0    f4(a_i,M,c)
 *   0 1    f2(b_i,M)
 * 0 1 1    f4(a_i,M-sB,c)+2^t
 * 1.0 0    2^t-1
 * 1.  0    f3(b_i,M-sA,2^t-c)+2^t if c > 0
 * 1.1 1    f4(a_i,M-sB,c)+2^t
 */