Problem Description

Note: We provide a brief, formal statement at the end of the description.

City C is a capital of magic, famous for its top-level wizards. For a wizard, the most important things are, of course, the magic wand and the magic crystals embedded in it.

Each magic wand and each magic crystal can be measured by a magic value. The magic value of a wand is the minimum magic value among all crystals embedded in it.

Apprentice wizard little $\omega$ from City C wants to strengthen his wand. Before strengthening, his wand has $n$ crystals embedded, whose magic values are $a_1,a_2,\dots,a_n$.

Little $\omega$ plans to use a powerful secret technique once to strengthen his wand. In this technique, he may choose any $x$, and then change every crystal’s magic value from $a_i$ to $(a_i \oplus x)$, where $\oplus$ denotes bitwise XOR. Due to little $\omega$’s limited ability, $a_1,a_2,\dots,a_n$ and $x$ are all integers in $[0,2^k-1]$.

Little $\omega$ also finds that this technique can be strengthened in a targeted way. Specifically, he can spend $b_i$ stamina to apply targeted strengthening to the $i$-th crystal, changing its value from what would become $(a_i \oplus x)$ into $(a_i+x)$. Since little $\omega$ is limited, the total stamina spent on targeted strengthening cannot exceed $m$, and each crystal can be targeted at most once.

Little $\omega$ wants to know the maximum possible magic value of the wand after strengthening. He cannot compute it, so please help him.

Formally: Given $a_1,a_2,\dots,a_n$ and $b_1,b_2,\dots,b_n$, where $a_i \in [0,2^k-1]$ and $b_i\geq 0$, you need to find $S \subseteq \{1,2,\dots,n\}$ and $x \in [0,2^k-1]$ satisfying:

• $\sum \limits_{i\in S} b_i\leq m$;
• Under the above constraint, maximize $val(S,x)=\min(\min \limits_{i \in S}(a_i+x),\min \limits_{i \in U \backslash S}(a_i \oplus x))$.

You only need to output the maximum value of $val(S,x)$.

Input Format

This problem has multiple test cases. The first line contains two integers $c,T$, denoting the subtask index and the number of test cases. In the samples, $c$ means the constraints are the same as those of subtask $c$.

Then for each test case:

• The first line contains three integers $n,m,k$.
• The second line contains $n$ integers $a_1,a_2,\dots,a_n$, representing the initial magic values of the crystals.
• The third line contains $n$ integers $b_1,b_2,\dots,b_n$, representing the stamina cost of targeted strengthening for each crystal.

Output Format

For each test case, output one integer per line: the maximum magic value little $\omega$ can obtain for the wand.

1 2
5 2 3
1 1 2 3 7
1 1 0 3 2
1 1 1
1
0

5
2

Hint

[Sample 1 Explanation]

• For the first test case, one feasible plan is: apply targeted strengthening to crystal $5$ (i.e. $S=\{5\}$) and choose $x=4$. The final crystal magic values are $5,5,6,7,11$, so the wand’s magic value is $5$. It can be proven that no better plan exists.
• For the second test case, one feasible plan is: apply targeted strengthening to crystal $1$ (i.e. $S=\{1\}$) and choose $x=1$.

[Sample 2]

See the attached xor2.in/ans.

This sample satisfies $c=4$.

[Sample 3]

See the attached xor3.in/ans.

This sample satisfies $c=7$.

[Sample 4]

See the attached xor4.in/ans.

This sample satisfies $c=9$.

[Sample 5]

See the attached xor5.in/ans.

This sample satisfies $c=11$.

[Sample 6]

See the attached xor6.in/ans.

This sample satisfies $c=14$.

[Sample 7]

See the attached xor7.in/ans.

This sample satisfies $c=22$.

[Subtasks]

Let $\sum n$ be the sum of $n$ over all test cases in a test file. For all testdata:

• $T \geq 1$;
• $1 \leq n \leq 10^5$, $1 \leq \sum n \leq 5\times 10^5$;
• $0 \leq m \leq 10^9$;
• $0 \leq k \leq 120$;
• $\forall 1 \leq i \leq n, 0 \leq a_i<2^k$;
• $\forall 1 \leq i \leq n, 0 \leq b_i \leq 10^9$.

• Special Property A: $m=0$; $\forall 1 \leq i\le n, b_i\geq 1$.
• Special Property B: $m=1$; $\forall 1 \leq i\le n, b_i \in \{1,2\}$, and at most one $i$ satisfies $b_i=1$.
• Special Property C: $m=1$; $\forall 1 \leq i\le n, b_i \in \{1,2\}$.

[Notes]

The input file of this problem is large, so please use a faster input method.

In the judging environment, you may use the $128$-bit signed integer type __int128, which can store integers in $[-2^{127},2^{127}-1]$. Its usage is basically the same as other integer types.

Note that this type cannot be read or written using common I/O methods such as cin/cout or scanf/printf. We provide an implementation of __int128 I/O functions in the contestant directory for you to use.

Translated by ChatGPT 5