Kevin and And
Contest: IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2)
Difficulty rating: 2000
Tags: bitmasks, brute force, dp, greedy, math, sortings

Kevin has an integer sequence $$$a$$$ of length $$$n$$$. At the same time, Kevin has $$$m$$$ types of magic, where the $$$i$$$-th type of magic can be represented by an integer $$$b_i$$$.

Kevin can perform at most $$$k$$$ (possibly zero) magic operations. In each operation, Kevin can do the following:

- Choose two indices $$$i$$$ ($$$1\leq i\leq n$$$) and $$$j$$$ ($$$1\leq j\leq m$$$), and then update $$$a_i$$$ to $$$a_i\ \&\ b_j$$$. Here, $$$\&$$$ denotes the bitwise AND operation.

Find the minimum possible sum of all numbers in the sequence $$$a$$$ after performing at most $$$k$$$ operations.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n, m, k$$$ ($$$1\leq n \leq 10^5$$$, $$$1\leq m \leq 10$$$, $$$0\leq k\leq nm$$$) — the length of $$$a$$$, the number of types of magic, and the maximum number of operations.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i < 2^{30}$$$).

The third line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$0\leq b_i < 2^{30}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, output one integer — the minimum possible sum of all numbers in the sequence $$$a$$$ after performing at most $$$k$$$ operations.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, one possible way could be:

- Update $$$a_1$$$ to $$$a_1\ \&\ b_1$$$. The sequence will become $$$[5]$$$.
- Update $$$a_1$$$ to $$$a_1\ \&\ b_3$$$. The sequence will become $$$[1]$$$.

In the second test case, one possible way could be:

- Update $$$a_1$$$ to $$$a_1\ \&\ b_3$$$. The sequence will become $$$[1, 6]$$$.
- Update $$$a_2$$$ to $$$a_2\ \&\ b_3$$$. The sequence will become $$$[1, 2]$$$.

Example input:
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

Example output:
1
3
11
5368709115
0

Editorial:
For a fixed $$$p$$$, let $$$f(S)$$$ represent the number obtained after applying the operations in set $$$S$$$ to $$$p$$$. Define $$$g(i)$$$ as the minimum value of $$$f(S)$$$ for all subsets $$$S$$$ with $$$|S| = i$$$, i.e., $$$g(i) = \min_{|S| = i} f(S)$$$.
—
Lemma: The function $$$g$$$ is convex, that is for all $$$i$$$ ($$$1 \leq i < m$$$), the inequality $$$2g(i) \leq g(i-1) + g(i+1)$$$ holds.
Proof: Let $$$f(S)$$$ be the value corresponding to the minimum of $$$g(i-1)$$$, and let $$$f(T)$$$ correspond to the minimum of $$$g(i+1)$$$. Suppose the $$$w$$$-th bit is the highest bit where $$$f(S)$$$ and $$$f(T)$$$ differ.
We can always find an operation $$$y \in T \setminus S$$$ that turns the $$$w$$$-th bit in $$$g(i-1)$$$ into $$$0$$$. In this case, we have: $$$$$$g(i - 1) - f(S \cup \{y\}) \geq 2^w.$$$$$$
Moreover, since the highest bit where $$$f(S \cup {y})$$$ and $$$g(i+1)$$$ differ is no greater than $$$w-1$$$, we have: $$$$$$f(S \cup \{y\}) - g(i + 1) \leq 2^w.$$$$$$
Combining these inequalities gives: $$$$$$2 g(i) \leq 2 f(S \cup \{y\}) \leq g(i - 1) + g(i + 1),$$$$$$ proving the convexity of $$$g$$$.
—
For each number $$$a_i$$$, we can use brute force to compute the minimum value obtained after applying $$$j$$$ operations, denoted as $$$num(i, j)$$$. From the lemma, we know that the difference $$$num(i, k) - num(i, k - 1)$$$ is non-increasing.
Thus, when performing operations on this number, the reductions in value are:
$$$$$$num(i, 0) - num(i, 1), num(i, 1) - num(i, 2), \dots, num(i, m - 1) - num(i, m).$$$$$$
You need to perform $$$k$$$ operations in total. To minimize the result, you can choose the $$$k$$$ largest reductions from all possible operations. This can be done by sorting all operations by their cost or by using std::nth_element.
Time complexity: $$$O(n2^m + nm)$$$。