Description

The shape of each painting can be abstracted as $n$ cells in a row, where the $i$-th cell has a weight $a_i$.

xtq has enough paintbrushes of different colors. Each time he uses one brush, he can paint a continuous segment on the cells with length at least $k$, and then switch to another brush and continue painting starting from the next cell, where $k<n$.

To test xtq’s painting skills, the art teacher sets some challenges.

He may start painting from any cell between $1$ and $k$ (inclusive) and paint all the way to cell $n$. If he starts from cell $i$, he gains an initial score of $b_i$.

Suppose xtq uses the same brush to paint continuously from cell $i$ to cell $j$. Then he gains a score of $(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)$, where $\gcd$ denotes the greatest common divisor.

Now, xtq wants to find a plan for using the brushes so that for each painting he needs to copy, his total score is as large as possible.

Input Format

The first line contains a positive integer $T$, representing the number of paintings.

For each painting:

The first line contains two positive integers $n, k$.

The second line contains $n$ positive integers $a_1, a_2, a_3, \ldots , a_n$.

The third line contains $k$ integers $b_1, b_2, b_3, \ldots , b_k$.

Output Format

For each painting, output one integer, representing the maximum score xtq can obtain after completing this painting.

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

31

Hint

Sample explanation:

xtq can start from $1$ and gain an initial score of $6$ points. The first segment is $[1,2]$, gaining $5$ points; the second segment is $[3,4]$, gaining $10$ points; the third segment is $[5,6]$, gaining $10$ points. In total, $31$ points.

Constraints:

For $20\%$ of the testdata, $n\le 10$.
For $40\%$ of the testdata, $n\le 3000$.
For $70\%$ of the testdata, $n\le 30000$.
For $100\%$ of the testdata, $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}$.

The testdata has multiple levels, so it should not be too strict on constant factors.

Translated by ChatGPT 5