#545. 「LibreOJ β Round #7」小埋与游乐场

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Snakes

题目描述

阿历克斯附体的希尔芬、崩巴附体的切绘、蒸汽姬海老名与全能少女小埋在游乐场玩旋转咖啡杯。双鱼座的切绘占卜得到的幸运数字是 3 ,然而在游乐场却没有编号为 3 的旋转咖啡杯。全能少女小埋想到了办法,旋转咖啡杯的编号构成了一个整数集合,小埋也给出了一个整数集合,并定义了一个操作。现在,她想知道操作后的旋转咖啡杯编号的最低位之和是多少,如果是 3 ,那么她就可以带着切绘去坐旋转咖啡杯啦!

(以上内容与题目内容无必然联系)

有两个非负整数组成的可重集合 A B

现在你可以对 A 至多 k 个元素进行操作。操作方法为:设你准备操作且未被操作过 A 中的元素是 a ,你可以在 B 中选取任意一个元素 b ,将 a 修改为 a\oplus b (这里 \oplus 表示二进制按位异或),然后从 B 删去 b

最终,你要使 A 中所有元素的 \mathrm{lowbit} 之和最小。正整数的 \mathrm{lowbit} 定义为其二进制最低非零位的值 0 \mathrm{lowbit} 规定为 0 ,例如 \mathrm{lowbit}(0)=0,\mathrm{lowbit}(1)=1,\mathrm{lowbit}(24)=8 。形式化地有:

\mathrm{lowbit}(x)= \begin{cases} \max(\{2^k:k\in \mathbb{N},2^k|x\}) & x\in \mathbb{N}^+\\ 0 & x=0 \end{cases}

(其中 | 表示整除)

你需要求出操作后 A 中所有元素的 \mathrm{lowbit} 之和的可能的最小值。

输入格式

第一行一个整数 n 表示 A 的元素个数。
接下来一行 n 个整数 \{a_i\} 表示 A 中元素。
接下来一行一个整数 m 表示 B 的元素个数。
接下来一行 m 个整数 \{b_i\} 表示 B 中元素。
接下来一行一个整数 k

输出格式

输出一行一个整数 S 表示操作后 A 中所有元素的 \mathrm{lowbit} 之和的可能的最小值。

样例

样例输入

5
6 18 14 1 13
5
7 7 8 8 15
3

样例输出

5

样例解释

\{6,18,14,1,13\} \mathrm{lowbit} 分别为 2,2,2,1,1 ,将 6,18,14 分别与 7,7,15 操作,得到新集合为 \{1,21,1,1,13\} ,其 \mathrm{lowbit} 分别为 1,1,1,1,1 ,答案为 5

数据范围与提示

对于所有数据, 1\le n,m,k\le 1.2\times 10^6,0\le a_i,b_i\le 10^9

Subtask # 分值 n,m k 特殊性质
1 6 1\le n,m\le 8 1\le k\le 8
2 8 1\le n,m\le 10^6 k=1 没有元素同时在 A,B 中出现
3 10
4 9 1\le n,m\le 500 1\le k\le 500 没有元素同时在 A,B 中出现
5 11
6 9 1\le n,m\le 10^6 1\le k\le 10^6 B 中元素均相等
7 13 1\le n,m\le 5\times 10^3 1\le k\le 5\times 10^3
8 15 1\le n,m\le 3\times 10^5 1\le k\le 3\times 10^5
9 19 1\le n,m\le 1.2\times 10^6 1\le k\le 1.2\times 10^6