強激光發射機構

#include <bits/stdc++.h>
#define ll __int128
#define int long long
using namespace std;
inline ll read() {
ll x = 0, f = 1;
char c = getchar();
while (c < '0' || '9' < c) {
if (c == '-') f = -1;
c = getchar();
}
while ('0' <= c && c <= '9') {
x = x * 10 + (ll)(c - '0');
c = getchar();
}
return x * f;
}
inline void write(ll x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}

const int N = 500005, M = 12000005;
const ll INF = ((ll)1) << ((ll)120);

int n, m, k;
int b[N], ch[M][2], tot, sumb[M];
ll a[N], mina[M], mainans;

inline int add() {
tot++;
ch[tot][0] = ch[tot][1] = 0;
mina[tot] = (ll)1 << k;
sumb[tot] = 0;
return tot;
}

inline void insert(ll a, int b) {
int pos = 1, c;
mina[pos] = min(mina[pos], a);
sumb[pos] += b;
for (int i = k - 1; ~i; i--) {
c = a >> i & 1;
if (ch[pos][c] == 0) ch[pos][c] = add();
pos = ch[pos][c];
mina[pos] = min(mina[pos], a);
sumb[pos] += b;
}
}

inline void solve(int pos, int dep, ll amin, int bsum, ll x, ll ans) {
if (dep == -1) {
mainans = max(mainans, ans);
return;
}
ll base = (ll)1 << dep, all = base - 1;
if (!pos) {
mainans = max(mainans, amin + (x | all | base));
return;
}

bool f = false; // ans can be 1
if (bsum + sumb[ch[pos][0]] <= m && min(amin, mina[ch[pos][0]]) + (x | all) >= (ans | base)) {
    solve(ch[pos][1], dep - 1, min(amin, mina[ch[pos][0]]), bsum + sumb[ch[pos][0]], x, ans | base);
    f = true;
}
if (bsum + sumb[ch[pos][1]] <= m && min(amin, mina[ch[pos][1]]) + (x | all | base) >= (ans | base)) {
    solve(ch[pos][0], dep - 1, min(amin, mina[ch[pos][1]]), bsum + sumb[ch[pos][1]], x | base, ans | base);
    f = true;
}
if (f) return;
solve(ch[pos][0], dep - 1, amin, bsum, x, ans);
solve(ch[pos][1], dep - 1, amin, bsum, x | base, ans);

}

inline void work() {
scanf("%lld %lld %lld", &n, &m, &k);
ll maxa = (ll)1 << k;
for (int i = 1; i <= n; i++) {
a[i] = read();
}
for (int i = 1; i <= n; i++) {
scanf("%lld", &b[i]);
}
mainans = 0;
tot = 0;
add();
mina[0] = maxa;
for (int i = 1; i <= n; i++) insert(a[i], b[i]);
if (sumb[1] <= m) { // special test
write(mina[1] + maxa - 1);
putchar('\n');
return;
}
solve(1, k - 1, maxa, 0, 0, 0);
write(mainans);
putchar('\n');
}

signed main() {

int c, T;
scanf("%lld %lld", &c, &T);
while (T--) work();   
return 0;

}