P10218 [NOI Qualifier Joint Contest 2024] Magic Wand

**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)$.

**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.

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

**[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