Painting Partition Challenge

You are given a painting represented by a row of n cells, where the i-th cell has a weight a_i (an integer). You have an unlimited supply of paint pens, each of a different color. When you use a pen, you can paint a contiguous segment of cells of length at least k (k < n). Once you finish a segment with one pen, you must switch to a different pen to paint the next segment starting from the cell immediately after the previous segment.

The art teacher sets the following challenge: You may choose a starting cell from among cells 1 to k (i.e. any i with 1 ≤ i ≤ k) and paint continuously up to cell n. Moreover, if you choose to start at cell i, you are awarded a bonus score of b_i.

For each pen stroke that paints a contiguous segment from cell i to cell j (with j − i + 1 ≥ k), you obtain a score calculated as follows:

$$f(i,j)=\bigl(a_i \;\mathrm{OR}\; a_{i+1} \;\mathrm{OR}\; \cdots \;\mathrm{OR}\; a_j\bigr) + \bigl(a_i \;\mathrm{AND}\; a_{i+1} \;\mathrm{AND}\; \cdots \;\mathrm{AND}\; a_j\bigr) + \gcd(a_i,a_{i+1},\ldots,a_j) $$

Your task is to determine an arrangement of pen strokes – that is, a segmentation of the cells from your chosen starting cell to cell n (where each segment has length at least k) – in order to maximize the total score. The total score is the sum of the bonus (based on the starting cell) and the scores obtained from each segment painted.

Note: The bitwise operators OR and AND refer to the standard bitwise operations on integers, and gcd denotes the greatest common divisor.

inputFormat

The first line contains two integers n and k (with k < n).

The second line contains n integers: a₁, a₂, ..., a_n representing the weight of each cell.

The third line contains k integers: b₁, b₂, ..., b_k where b_i is the bonus score when starting from cell i.

outputFormat

Output a single integer — the maximum total score achievable.

sample

5 2
1 2 3 4 5
5 6

22