P13714 Elimination (Hard ver.)

> The storyline you've written isn't one I wish to perform. > > 你书里的剧情 我不想上演 > > I'd rather the curtain fall on a comedy. > > 因为我喜欢喜剧收尾

Given two numbers $x, y$ and four arrays $a, b, c, d$ of length $n$, you can perform the following two operations on $x$ any number of times: - For any $i$ ($1 \leq i \leq n$), pay a cost of $c_i$ to assign $x \leftarrow x \operatorname{AND} a_i$. - For any $i$ ($1 \leq i \leq n$), pay a cost of $d_i$ to assign $x \leftarrow x \operatorname{OR} b_i$. Where $\operatorname{AND}$ and $\operatorname{OR}$ represent **bitwise AND** and **bitwise OR** operations respectively. You need to determine the minimum cost to transform $x$ into $y$. If it is impossible, output $-1$. [Help: What are bitwise AND and bitwise OR?](https://en.wikipedia.org/wiki/Bitwise_operation)

**This problem contains multiple test cases.** The first line of input contains an integer $T$, indicating the number of test cases. This is followed by $T$ test cases, each formatted as follows: The first line contains four integers $n, k, x, y$, where $n, x, y$ are as described in the problem statement. $k$ indicates that for this test case, $0 \le x, y, a_i, b_i < 2^k$, and $1 \le n \le 2^k$. The second line contains $n$ integers, representing $a_1, a_2, \dots, a_n$. The third line contains $n$ integers, representing $b_1, b_2, \dots, b_n$. The fourth line contains $n$ integers, representing $c_1, c_2, \dots, c_n$. The fifth line contains $n$ integers, representing $d_1, d_2, \dots, d_n$.

For each test case, output one integer, representing the answer.

### Sample Explanation For Sample #1: - For the first test case, you can spend a cost of $13$ to perform a bitwise AND with $0$, meeting the requirement. It can be proven that no better solution exists. - For the second test case, it can be proven that no solution exists. ### Data Constraints **This problem uses subtask bundling/dependencies.** - Subtask 0 (0 pts): Sample cases. - Subtask 1 (10 pts): $\sum 2^{k} \le 2^{3}$. - Subtask 2 (20 pts): $\sum 2^{k} \le 2^{8}$. Depends on subtask $1$. - Subtask 3 (20 pts): $\sum 2^k \le 2^{14}$. Depends on subtasks $1, 2$. - Subtask 4 (50 pts): No additional constraints. Depends on subtasks $0 \sim 3$. For all data, it is guaranteed that $1 \le k \le 16$, $2 \le \sum 2^k \le 2^{16}$, and $1 \le c_i, d_i \le 10^9$.