Background

When xtq was in fourth grade, he got a set of magical paintbrushes. To test how powerful the brushes were (and to show off his strong artistic talent), he decided to copy several paintings for his art teacher.

Problem 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