Description

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?

Input Format

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$.

Output Format

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

2
4 3 1 0
1 1 0 1
0 1 0 0
20 16 13 18
18 19 3 2
1 2 0 2
1
1
9
20

13
-1

3
2 10 190 256
973 290
349 836
19 9
73 72
4 10 530 187
973 290 416 734
349 187 359 377
36 13 9 28
27 47 21 45
8 10 344 264
973 290 416 734 296 269 947 449
349 187 664 308 31 177 852 787
79 68 50 70 3 84 63 37
35 86 23 63 79 89 48 22

100
56
3

1
3 16 1881 11917
48233 11933 53742
31630 57818 35460
897 440 983
579 162 597

1916

1
6 16 51577 4
47059 26620 59157 582 58780 19807 
60097 28458 287 10757 55031 15727 
1 1 1 1 1 1 
1 1 1 1 1 1 

3

Hint

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$.