问题 I: 切割木材

染染船长，亲自上阵！

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

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

分割木材都在其整数米处分割，分割后会分成若干段，每个段实际上可以表示为参数序列 a1,a2,⋯,ana1,a2,⋯,an 上的某个区间 al,al+1,⋯,aral,al+1,⋯,ar。

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

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

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

对于一个分割方案，假设其具有 $k$ 次分割，分割位置从左往右分别为第 p1,p2,⋯,pkp1,p2,⋯,pk 米处，则最终整个分割方案的价值为：g(f(1,p1))+g(f(p1+1,p2))+⋯+g(f(pk+1,n))g(f(1,p1))+g(f(p1+1,p2))+⋯+g(f(pk+1,n))

注意，这里 $k$ 可以为 $0$，同时要求 0<p1<p2<⋯<pk<n0<p1<p2<⋯<pk<n。

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

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

输入第一行一个正整数 $T(1\le T\le 20)$，表示数据组数。

每组数据第一行两个非负整数 n (1≤n≤105)n (1≤n≤105) 和 $m(0\le m\le 20)$，分别表示木材的长度和参数范围。

第二行 $n$ 个非负整数 a1,a2,⋯,an (0≤ai<2m)a1,a2,⋯,an (0≤ai<2m)，表示参数序列。

第三行 2m2m 个整数 g(0),g(1),⋯,g(2m−1) (−109≤g(i)≤109)g(0),g(1),⋯,g(2m−1) (−109≤g(i)≤109)，表示函数 $g(x)$ 的取值。

保证单个测试点内每组数据中 $n$ 的和不超过 106106，2m2m 的和不超过 222222。