Max Heat ~ WildLife-TK

Kiteretsu goes to his Chemistry Lab to perform the perfect reaction. In his lab, he found

$N$ reagents numbered $1$ to $N$ . The $i^{t h}$ reagent has two properties - $A_{i}$ and $B_{i}$ .

A reaction can be performed between the reagents $i$ and $j$ only if $A_{i} \leq 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}, \dots, A_{N}$ .
Third line of each test case contains $N$ integers $B_{1}, B_{2}, \dots, 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 \leq T \leq 10$
$2 \leq N \leq 10^{6}$
$1 \leq D \leq 2000$
$(i + 1) \leq A_{i} \leq N$ $\forall$ $(1 \leq i < N)$
$A_{N} = N + 1$
$1 \leq B_{i} \leq N$
Sum of $N$ over all test cases does not exceed $10^{6}$ .

Sample Input 1

Sample Output 1

6
-7

Explanation

Test Case $1$ : Let us choose $i = 2$ and $j = 4$ . Since $A_{2} \leq 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} ≰ 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$ .

Max Heat