描述

染染船长，亲自上阵！

木材已经被运到船上了，然而直接一根不规则的木材是难以利用的，切割木材就是一道必要的工序了。

作为船长，染染要以身作则分割木材。于是染染挑了其中一根长为 $n$ 米的木材，其每一米上都标有正整数参数，从左往右第 $i$ 米的参数为 $a_i$，参数的范围在 $[0, 2^m)$ 内。

分割木材都在其整数米处分割，分割后会分成若干段，每个段实际上可以表示为参数序列 $a_1, a_2, \cdots, a_n$ 上的某个区间 $a_l, a_{l+1}, \cdots, a_r$。

对于分割后的一段 $a_l, a_{l+1}, \cdots, a_r$ 具有可计算参数 $f(l, r)$。$f(l, r)$ 在二进制下第 $k$ 位的值为 $1$ 的条件为 $a_l, a_{l+1}, \cdots, a_r$ 的第 $k$ 位既不完全为 $0$ 也不完全为 $1$，否则就为 $0$。

举个例子，比如对于序列 $0, 2, 1, 3, 5$，有 $f(3, 3) = 0, f(1, 2) = 2, f(3, 5) = 6$。

而实际上还有一个转换函数 $g(x)$，分割后的一段 $a_l, a_{l+1}, \cdots, a_r$ 的价值为 $g(f(l, r))$。不幸的是，$g(x)$ 是一个性质相当恶劣的函数，所以染染和手下的水手只能靠实验得到了 $g(x)$ 的在 $0, 1, \cdots, 2^m - 1$ 处的取值。

对于一个分割方案，假设其具有 $k$ 次分割，分割位置从左往右分别为第 $p_1, p_2, \cdots, p_k$ 米处，则最终整个分割方案的价值为：

$$g(f(1, p_1)) + g(f(p_1 + 1, p_2)) + \cdots + g(f(p_k + 1, n))$$

注意，这里 $k$ 可以为 $0$，同时要求 $0 < p_1 < p_2 < \cdots < p_k < n$。

现在，为了物尽其用，染染希望最大化分割方案的价值。

---

输入

本题单个测试点内包含多组测试数据。

• 输入第一行一个正整数 $T$ ($1 \leq T \leq 20$)，表示数据组数。
• 每组数据第一行两个非负整数 $n$ ($1 \leq n \leq 10^5$) 和 $m$ ($0 \leq m \leq 20$)，分别表示木材的长度和参数范围。
• 第二行 $n$ 个非负整数 $a_1, a_2, \cdots, a_n$ ($0 \leq a_i < 2^m$)，表示参数序列。
• 第三行 $2^m$ 个整数 $g(0), g(1), \cdots, g(2^m - 1)$ ($-10^9 \leq g(i) \leq 10^9$)，表示函数 $g(x)$ 的取值。

保证单个测试点内每组数据中 $n$ 的和不超过 $10^6$，$2^m$ 的和不超过 $2^{22}$。

---

输出

对于每组数据输出一行一个整数，表示分割方案价值的最大值。

---

1
5 2
1 2 1 2 0
0 1 3 2

5

提示

最优方案是分成 $1, 2, 3$ 和 $4, 5$ 两段，答案为：

$$g(f(1, 3)) + g(f(4, 5)) = g(3) + g(2) = 2 + 3 = 5 ``` ---$$