#include <bits/stdc++.h> #define mxn 100003
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define rept(i, a, b) for (int i = a; i < b; ++i)
#define drep(i, a, b) for (int i = a; i >= b; --i)
using namespace std; inline int read() { int x = 0; char c = getchar(); while (!isdigit(c)) c = getchar(); while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return x; } inline __int128 read1() { __int128 x = 0; char c = getchar(); while (!isdigit(c)) c = getchar(); while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return x; } inline void print(__int128 a) { if (a > 9) print(a / 10); putchar(a % 10 + '0'); } int c, T, n, m, k, b, sm, tot, f[mxn * 120], t[mxn * 120][2]; __int128 a, mn, pw[123], A[mxn], s[mxn * 120]; void ins() { int p = 0; drep(i, k - 1, 0) { if (!t[p][(a >> i) & 1]) t[p][(a >> i) & 1] = ++tot, f[tot] = 0, s[tot] = a; p = t[p][(a >> i) & 1], f[p] = min(f[p] + b, m + 1), s[p] = min(s[p], a); } } __int128 solve(__int128 mid, int x, int d, __int128 now, __int128 mn, int sum, bool fl) { if (sum > m) return 0; if (d < 0) return mid; __int128 ans = 0; if (pw[d] - 1 + (fl && t[x][1] ? min(mn, s[t[x][1]]) : mn) + now >= mid) { ans = max(ans, solve(mid + pw[d], fl ? t[x][0] : 0, d - 1, now + pw[d], fl && t[x][1] ? min(mn, s[t[x][1]]) : mn, min(sum + (fl ? f[t[x][1]] : 0), m + 1), fl && t[x][0])); } if (pw[d] - 1 + (fl && t[x][0] ? min(mn, s[t[x][0]]) : mn) + now >= mid + pw[d]) { ans = max(ans, solve(mid + pw[d], fl ? t[x][1] : 0, d - 1, now, fl && t[x][0] ? min(mn, s[t[x][0]]) : mn, min(sum + (fl ? f[t[x][0]] : 0), m + 1), fl && t[x][1])); } if (ans) return ans; if (pw[d] - 1 + mn + now >= mid) { ans = max(ans, solve(mid, fl ? t[x][0] : 0, d - 1, now, mn, sum, fl && t[x][0])); } if (pw[d + 1] - 1 + mn + now >= mid) { ans = max(ans, solve(mid, fl ? t[x][1] : 0, d - 1, now + pw[d], mn, sum, fl && t[x][1])); } return ans; } signed main() { c = read(), T = read(); pw[0] = 1; rep(i, 1, 120) pw[i] = pw[i - 1] * 2; while (T--) { n = read(), m = read(), k = read(); rep(i, 0, tot) t[i][0] = t[i][1] = 0; tot = 0; sm = 0, mn = pw[k]; rep(i, 1, n) A[i] = read1(); rep(i, 1, n) { b = read(), a = A[i]; ins(); sm = min(sm + b, m + 1), mn = min(mn, a); } if (sm <= m) { print(mn + pw[k] - 1); puts(""); continue; } print(solve(0, 0, k - 1, 0, pw[k], 0, 1)); puts(""); } return 0; }