Kiteretsu goes to his Chemistry Lab to perform the perfect reaction.
In his lab, he found N reagents numbered 1 to N. The i^{th} reagent has two properties - A_{i} and B_{i}.

A reaction can be performed between the reagents i and j only if A_{i} ≤ j.

If a reaction is performed between reagents i and $j, i \cdot j$ amount of heat is produced. Out of this$, D \cdot (B_{i} \oplus B_{j})$ is absorbed and the rest heat is released. Here, $\oplus$ denotes the [bitwise XOR] operation.

More formally, in a reaction between reagents i and j, the heat released is given by:
$H(i,j)= i \cdot j - D \cdot (B_{i} \oplus B_{j})$

Find the maximum possible heat which can be released in a reaction.

Note: The input of this problem is large, so use fast input/output methods.

------ Input Format ------

• The first line will contain T - the number of test cases. Then the test cases follow.
• First line of each test case contains two integers N, D.
• Second line of each test case contains $N integers A_{1}, A_{2}, \ldots, A_{N}$.
• Third line of each test case contains $N integers B_{1}, B_{2}, \ldots, B_{N}$

------ Output Format ------

For each test case, print a single line, a single integer denoting the maximum possible heat that can be released in a reaction.

------ Constraints ------

$1 ≤ T ≤ 10$
$2 ≤ N ≤ 10^{6}$
$1 ≤ D ≤ 2000$
$(i+1) ≤ A_{i} ≤ N$ $\forall$ $(1 ≤ i < N)$
$A_{N}=N+1$
$1 ≤ B_{i} ≤ N$
- Sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------
2
5 2
2 4 5 5 6
1 3 2 2 5
2 3
2 3
1 2

----- Sample Output 1 ------
6
-7

----- explanation 1 ------
Test Case $1$: Let us choose $i = 2$ and $j = 4$. Since $A_{2} ≤ 4$, a reaction can take place.
The heat released in this reaction is $2\cdot 4 - 2\cdot (3 \oplus 2) = 8-2 \cdot 1 = 6$. It can be proven that for no other reaction, the heat released is greater than $6$.
Some other reactions can take place between $(2, 5)$, $(3,5)$. Note that no reaction is possible between $(3,4)$ as $A_{3} \nleq 4$.

Test Case $2$: The only possible reaction is between reagents $1$ and $2$. The heat released in this reaction is $1 \cdot 2 - 3\cdot (1 \oplus 2) = 2 - 3\cdot 3 = -7$.

见题面

见题面