题目背景

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}$。

数据有梯度，应该不太卡常。