← 返回题目列表

Codeforces · 2061/E

E. 凯文和安

中文机器翻译题面 查看原题

Kevin 有一个长度为 $$$n$$$ 的整数序列 $$$a$$$。同时,凯文有$$$m$$$种魔法,其中第$$$i$$$种魔法可以用整数$$$b_i$$$表示。

Kevin 最多可以执行 $$$k$$$(可能为零)个魔法操作。在每个操作中,Kevin 可以执行以下操作:

- 选择两个索引 $$$i$$$ ($$$1\leq i\leq n$$$) 和 $$$j$$$ ($$$1\leq j\leq m$$$),然后将 $$$a_i$$$ 更新为 $$$a_i\ \&\ b_j$$$。其中$$$\&$$$表示按位与运算。

在执行最多 $$$k$$$ 操作后,找出序列 $$$a$$$ 中所有数字的最小可能总和。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n, m, k$$$ ($$$1\leq n \leq 10^5$$$, $$$1\leq m \leq 10$$$, $$$0\leq k\leq nm$$$) — $$$a$$$ 的长度、魔法类型的数量和最大操作数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i < 2^{30}$$$)。

第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$0\leq b_i < 2^{30}$$$)。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,输出一个整数——执行最多 $$$k$$$ 操作后序列 $$$a$$$ 中所有数字的最小可能总和。

示例

输入 #1

5
1 3 2
7
5 6 3
2 3 2
5 6
5 6 3
10 2 5
3 1 4 1 5 9 2 6 5 3
7 8
5 1 0
1073741823 1073741823 1073741823 1073741823 1073741823
1073741823
1 1 0
0
0

输出 #1

1
3
11
5368709115
0

注意

在第一个测试用例中,一种可能的方法是:

- 将 $$$a_1$$$ 更新为 $$$a_1\ \&\ b_1$$$。该序列将变为$$$[5]$$$。
- 将 $$$a_1$$$ 更新为 $$$a_1\ \&\ b_3$$$。该序列将变为$$$[1]$$$。

在第二个测试用例中,一种可能的方法是:

- 将 $$$a_1$$$ 更新为 $$$a_1\ \&\ b_3$$$。该序列将变为 $$$[1, 6]$$$。
- 将 $$$a_2$$$ 更新为 $$$a_2\ \&\ b_3$$$。该序列将变为 $$$[1, 2]$$$。