xtq 的神笔

xtq 在小学四年级的时候得到了一套神奇的画笔。为了测试神笔的威力（以及展现自己过人的艺术天赋），他决定先为美术老师临摹几幅画。

每幅画的形态可以抽象为排成一列的 $n$ 个格子，其中第 $i$ 个格子具有一个权值 $a_i$。 xtq 有足够多不同颜色的画笔，每当他使用一根笔，他可以在格子上画下至少长度为 $k$ 的连续一段，然后再换另一根笔从下一个格子继续画，其中 $k<n$。 美术老师为了考验 xtq 的绘画功力，为他设置了一些挑战。 他可以从 $1$ 到 $k$ 的任意一个格子开始画到编号为 $n$ 的格子，其中从第 $i$ 个格子开始会获得 $b_i$ 的得分。 假设 xtq 使用同一根画笔，从编号为 $i$ 的格子连续地画到编号为 $j$ 的格子，他就会获得（$a_i \mathbin{\mathrm{or}} a_{i+1} \mathbin{\mathrm{or}} a_{i+2} \mathbin{\mathrm{or}} \cdots \mathbin{\mathrm{or}} a_j) + (a_i \mathbin{\mathrm{and}} a_{i+1} \mathbin{\mathrm{and}} a_{i+2} \mathbin{\mathrm{and}} \cdots \mathbin{\mathrm{and}} a_j) + \gcd(a_i, a_{i+1}, a_{i+2}, \ldots, a_j)$ 的分数，其中 $\gcd$ 代表最大公约数。 现在，xtq 希望找到一种安排画笔使用的方案，使得对于每一幅需要临摹的画，他总共获得的分数尽量多。

第一行，一个正整数 $T$，表示画的数量。 对于每一幅画： 第一行，两个正整数 $n, k$。 第二行，$n$ 个正整数 $a_1, a_2, a_3, \ldots , a_n$。 第三行，$k$ 个整数 $b_1, b_2, b_3, \ldots , b_k$。

对于每一幅画，输出一个整数，代表 xtq 完成这幅画最多能获得的分数。

1
6 2
3 1 4 5 6 2
6 -2

31

样例解释： xtq 可以从 $1$ 开始，获得 $6$ 分初始得分；第一段画 $[1,2]$，获得 $5$ 分；第二段画 $[3,4]$，获得 $10$ 分；第三段画 $[5,6]$，获得 $10$ 分。共 $31$ 分。 对于 $20\%$ 的数据，$n\le 10$。 对于 $40\%$ 的数据，$n\le 3000$。 对于 $70\%$ 的数据，$n\le 30000$。 对于 $100\%$ 的数据，$1\le k<n\le 3 \times {10}^5$，$T\le 10$，$1\le a_i\le 2^{30}$，$-2^{30}\le b_i\le 2^{30}$。 数据有梯度，应该不太卡常。