分组

Problem Description

给定 $n$ 个正整数 $a_1,a_2,\dots,a_n$ ($1\leq a_i<2^m$) 以及 $0$ 到 $2^m-1$ 的权重 $w_0,w_1,\dots,w_{2^m-1}$；你需要把这 $n$ 个正整数分成四组 $A,B,C,D$，令 $f ( A ) , f ( B ) , f ( C ) , f ( D )$ 分别表示每组中所有数字的异或和，你的分组方案需要最小化 $w_{f(A)},w_{f(B)},w_{f(C)},w_{f(D)}$ 的极差，即：

$$\max\left(w_{f(A)},w_{f(B)},w_{f(C)},w_{f(D)}\right)-\min\left(w_{f(A)},w_{f(B)},w_{f(C)},w_{f(D)}\right) $$

注意：每组都可以为空，此时 $f ( \cdot ) = 0$。

Input

第一行包含一个正整数 $T$ ($1\leq T\leq 5$)，表示测试数据的组数。 每组数据第一行包含两个正整数 $n,m$ ($4\leq n\leq 18$, $1\leq m\leq 10$)。 第二行包含 $n$ 个正整数 $a_1,a_2,\dots,a_n$ ($1\leq a_i<2^m$)。 第三行包含 $2^m$ 个整数 $w_0,w_1,\dots,w_{2^m-1}$ ($0\leq w_i\leq 10^9$)。

Output

对于每组数据输出一行一个整数，即 $w_{f(A)},w_{f(B)},w_{f(C)},w_{f(D)}$ 的极差的最小可能值。

Sample Input

2
4 2
1 2 3 1
0 1 2 3
7 4
3 2 15 13 11 9 7
12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11

Sample Output

1
2

Source

2024“钉耙编程”中国大学生算法设计超级联赛（4）