Magical Wand Strengthening

C City is a magical metropolis famed for its top-tier wizards. For any wizard, the two most important artifacts are the magic wand and the magical crystals embedded within it.

Each magic wand and crystal is measured by its magic power. In particular, the magic power of a wand is determined by the minimum magic power among all its embedded crystals.

Little ω is an apprentice wizard in C City. Before enhancing his wand, it contains n magical crystals with magic powers a₁, a₂, …, a_n.

He plans to boost his wand using a powerful secret technique. In this technique, he may choose an arbitrary integer x in the range [0, 2^k - 1] and transform every crystal’s power from a_i to a_i ⊕ x (where ⊕ denotes bitwise XOR). Note that both a_i and x are in the range [0, 2^k - 1].

Moreover, the technique allows for directional enhancement. Specifically, for the i^th crystal, he may opt to spend b_i units of stamina so that instead of being transformed to a_i ⊕ x it becomes a_i + x. Each crystal can be enhanced in this way at most once, and the total stamina spent cannot exceed m.

After the transformation, the wand's magic power is defined as the minimum of the transformed crystal powers. Formally, let S ⊆ {1,2,…,n} be the set of crystals that receive directional enhancement (i.e. they become a_i + x), and let the remaining crystals (not in S) be transformed as a_i ⊕ x. Then the wand's power is given by:

\(\mathrm{val}(S,x)=\min\big(\min_{i\in S}(a_i+x),\;\min_{i\notin S}(a_i\oplus x)\big)\)

(If one of the two sets is empty, treat the corresponding minimum as +\(\infty\).)

Your task is to choose S and x (with x in [0, 2^k - 1]) so that the total stamina cost \(\sum_{i\in S}b_i\) does not exceed m and the value \(\mathrm{val}(S,x)\) is maximized. Output the maximum possible value of \(\mathrm{val}(S,x)\).

Formal Description: Given arrays a₁, a₂, …, a_n and b₁, b₂, …, b_n with a_i ∈ [0,2^k-1] and b_i ≥ 0, choose S ⊆ {1,2,…,n} and x ∈ [0,2^k-1] such that:

• \(\sum_{i\in S} b_i \le m\);
• \(\mathrm{val}(S,x)=\min\big(\min_{i\in S}(a_i+x),\;\min_{i\notin S}(a_i\oplus x)\big)\) is maximized.

You only need to output the maximum achievable value of \(\mathrm{val}(S,x)\).

inputFormat

The first line contains three integers n, m, and k.

The second line contains n integers: a₁, a₂, …, a_n.

The third line contains n integers: b₁, b₂, …, b_n.

outputFormat

Output a single integer — the maximum possible magic power of the strengthened wand.

sample

2 1 2
1 2
1 100

2

</p>