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]$$$。